Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-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.

Original languageEnglish
JournalGraphs and Combinatorics
Publication statusE-pub ahead of print - 24. Jul 2021

Bibliographical note

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


  • Cubic graphs
  • Graph decomposition
  • Thomassen’s conjecture


Dive into the research topics of 'Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs'. Together they form a unique fingerprint.

Cite this