Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs

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

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


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 subgraph minimum degree at least 1 and contains no path on 4 vertices.

TidsskriftGraphs and Combinatorics
StatusE-pub ahead of print - 24. jul. 2021

Bibliografisk note

Funding Information:
The research was initiated at the Structural graph theory workshop at Gułtowy, 24-28 June 2019 sponsored by ERC Starting Grant “CUTACOMBS Cuts and decompositions: algorithms and combinatorial properties”, grant agreement No 714704. The first author is supported by the Danish research council under grant number DFF-7014-00037B. The second author was supported by the grant no. 19-04113Y of the Czech Science Foundation (GAČR) and the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004). The third author was supported by the Danish Council for Independent Research, Natural Sciences, grant DFF-8021-00249, AlgoGraph.

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.


Dyk ned i forskningsemnerne om 'Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs'. Sammen danner de et unikt fingeraftryk.