Counterexamples to Thomassen's conjecture on decomposition of cubic\n graphs

2019/08/19 by Thomas Bellitto, Tereza Klimošová, Bellitto, Thomas +7
Engineering · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1908.06697

openalex publication_date 2019/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct an infinite family of counterexamples to Thomassen's conjecture\nthat the vertices of every 3-connected, cubic graph on at least 8 vertices can\nbe colored blue and red such that the blue subgraph has maximum degree at most\n1 and the red subgraph minimum degree at least 1 and contains no path on 4\nvertices.\n

Related

• Decomposition of cubic graphs related to Wegner's conjecture
• Bound vertices of longest paths between two vertices in cubic graphs
• Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen
• Decomposing planar cubic graphs
• Berge's conjecture for cubic graphs with small colouring defect