Counterexamples to Thomassen's conjecture on decomposition of cubic graphs

DOI10.1007/S00373-021-02380-ZMaRDI QIDQ2053720zbMATH OpenOpenAlexWikidataFDO

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

Publication date 30 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.06697

zbMATH Keywords

cubic graphsgraph decompositionThomassen's conjecture

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Decomposition of cubic graphs related to Wegner's conjecture
• Decomposition of 3-connected cubic graphs
• Decompositions of cubic traceable graphs
• Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs
• Counterexamples to three conjectures concerning perfect graphs
• On the cubicity of certain graphs
• Cubicity of threshold graphs
• On the anti-Kekulé problem of cubic graphs
• Splitter Theorems for Cubic Graphs
• A class of cubic graphs satisfying Berge conjecture

Cites work

• Decomposition of cubic graphs related to Wegner's conjecture
• The square of a planar cubic graph is 7-colorable

Cited in

(7)

• Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs
• Cuts in matchings of 3-connected cubic graphs
• Decomposition of cubic graphs related to Wegner's conjecture
• Jones' conjecture in subcubic graphs
• Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen
• scientific article; zbMATH DE number 4152413 (Why is no real title available?)
• Counterexamples to three conjectures concerning perfect graphs

This page was built for publication: Counterexamples to Thomassen's conjecture on decomposition of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2053720)