Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs

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

Research output: Contribution to journalJournal articleResearchpeer-review

34 Downloads (Pure)

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
Volume37
Issue number6
Pages (from-to)2595-2599
ISSN0911-0119
DOIs
Publication statusPublished - 2021

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