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 11 and the red subgraph has minimum degree at least 11 and contains no path with 33 edges. Thomassen's conjecture. Every 33-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 33-connected cubic counterexamples; related open cases include outerplanar, K4K_4-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

Never refreshed

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.