Thomassen's crumby coloring conjecture for 3-connected cubic graphs
Thomassen's crumby coloring conjecture for 3-connected cubic graphs
A crumby coloring of a graph is a red-blue vertex coloring in which the blue subgraph has maximum degree at most and the red subgraph has minimum degree at least and contains no path with edges. Thomassen's conjecture. Every -connected cubic graph has a crumby coloring. This conjecture was refuted by Bellitto, Klimošová, Merker, Witkowski and Yuditsky, who constructed an infinite family of -connected cubic counterexamples; related open cases include outerplanar, -minor-free and bipartite graph classes.
Sources & referencesView supporting material
Primary source
János Barát, Zoltán L. Blázsik and Gábor Damásdi, “Crumby colorings – red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen”, arXiv:2108.08118 (2022).
Additional references
2 papers in this index state this conjecture (2019–2021). The statement above is taken from the most recent of them; the others are arXiv:1908.06697.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.