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.
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.
Status
- Refuted: Thomas Bellitto, Tereza Klimošová, Martin Merker, Marcin Witkowski and Yelena Yuditsky. Counterexamples to Thomassen's conjecture on decomposition of cubic graphs (arXiv, 2019) https://arxiv.org/abs/1908.06697
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).
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
No solutions have been posted yet.