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

Abstract

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
ISSN0911-0119
DOIs
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.

Keywords

  • Cubic graphs
  • Graph decomposition
  • Thomassen’s conjecture

Fingerprint

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

Cite this