Recolouring conjecture for triangle-free graphs
Let be a triangle-free graph, let be its maximum degree, and let denote the number of colours in a proper colouring. A colouring is Kempe-recolourable when it can be transformed by Kempe changes, interchanging two colours on a connected bichromatic component.
Triangle-free recolouring conjecture. Any triangle-free graph is -recolourable for all
The threshold is motivated by the paper's optimal analysis of frozen-colouring obstructions in triangle-free graphs, and the conjecture is tight in view of constructions above the threshold. The recolouring statement itself remains open.
References
Primary source
Lucas De Meyer, Clément Legrand-Duchesne, Jared León, Tim Planken and Youri Tamitegama, “A Recolouring Version of a Conjecture of Reed”, arXiv:2502.10147 (2025).
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.