Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs

Autor: Tereza Klimošová, Thomas Bellitto, Martin Merker, Yelena Yuditsky, Marcin Witkowski

Publikováno v: Bellitto, T, Klimošová, T, Merker, M, Witkowski, M & Yuditsky, Y 2021, ' Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs ', Graphs and Combinatorics, vol. 37, no. 6, pp. 2595-2599 . https://doi.org/10.1007/s00373-021-02380-z
Graphs and Combinatorics

We construct an infinite family of counterexamples to Thomassen’s conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::31e92407e7b0faea118c28beaa570f21
https://portal.findresearcher.sdu.dk/da/publications/4ec8446a-a0e0-414a-ac69-4c46f566013d

A proof of the Barát–Thomassen conjecture

Autor: Tien-Nam Le, Stéphan Thomassé, Martin Merker, Ararat Harutyunyan, Julien Bensmail

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, 2017, 124, pp.39-55. ⟨10.1016/j.jctb.2016.12.006⟩
Bensmail, J, Harutyunyan, A, Le, T N, Merker, M & Thomassé, S 2017, ' A proof of the Barát-Thomassen conjecture ', Journal of Combinatorial Theory. Series B, vol. 124, pp. 39-55 . https://doi.org/10.1016/j.jctb.2016.12.006
Journal of Combinatorial Theory, Series B, Elsevier, 2017, 124, pp.39-55. ⟨10.1016/j.jctb.2016.12.006⟩

International audience; The Barát-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k T such that every k T-edge-connected graph with size divisible by m can be edge-decomposed into copies of T. So far this conje

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::460ca47b2158e26387d4951cb6aaa41e
https://doi.org/10.1016/j.jctb.2016.12.006

Gaps in the cycle spectrum of 3-connected cubic planar graphs

Autor: Martin Merker

Publikováno v: Merker, M 2021, ' Gaps in the cycle spectrum of 3-connected cubic planar graphs ', Journal of Combinatorial Theory. Series B, vol. 146, pp. 68-75 . https://doi.org/10.1016/j.jctb.2020.08.002

We prove that, for every natural number k, every sufficiently large 3-connected cubic planar graph has a cycle whose length is in [ k , 2 k + 9 ] . We also show that this bound is close to being optimal by constructing, for every even k ≥ 4 , an in

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d2aab4a1267ae5c6c1dc54425d5f8037
http://arxiv.org/abs/1905.09101

Spanning trees without adjacent vertices of degree 2

Autor: Martin Merker, Kasper Szabo Lyngsie

Publikováno v: Lyngsie, K S & Merker, M 2019, ' Spanning trees without adjacent vertices of degree 2 ', Discrete Mathematics, vol. 342, no. 12, 111604 . https://doi.org/10.1016/j.disc.2019.111604

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number d such tha

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f3b4a430d6c00b7ee0ed7c5e7936ce29

Decomposing graphs into a constant number of locally irregular subgraphs

Autor: Julien Bensmail, Carsten Thomassen, Martin Merker

Publikováno v: European Journal of Combinatorics
European Journal of Combinatorics, Elsevier, 2017, 60, pp.124-134. ⟨10.1016/j.ejc.2016.09.011⟩
Bensmail, J, Merker, M & Thomassen, C 2016, ' Decomposing graphs into a constant number of locally irregular subgraphs ', European Journal of Combinatorics, vol. 60, pp. 124-134 . https://doi.org/10.1016/j.ejc.2016.09.011
European Journal of Combinatorics, 2017, 60, pp.124-134. ⟨10.1016/j.ejc.2016.09.011⟩

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index χ irr ′ ( G ) of a graph G is the smallest number of locally irregular subgraphs needed to edge-decompose G . Not all graphs have such a d

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9c70dfc619975b31debd0fbbb6de2f81
https://hal.archives-ouvertes.fr/hal-01629938/file/LocIrr0709.pdf