Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen

DOI10.1016/j.disc.2022.113281OpenAlexW3195649555WikidataQ123155820 ScholiaQ123155820MaRDI QIDQ2685314

Gábor Damásdi, János Barát, Zoltán L. Blázsik

Publication date: 21 February 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

outerplanar graphssubcubic graphsgraph coloringsWegner's conjecturesubdivisions of graphs

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Proof of Toft's conjecture: Every graph containing no fully odd \(K_4\) is 3-colorable
• The square of a planar cubic graph is 7-colorable
• Decomposition of cubic graphs related to Wegner's conjecture
• Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
• Paths, Trees, and Flowers
• Totally odd \(K_4\)-subdivisions in 4-chromatic graphs

This page was built for publication: Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen