Recolouring conjecture for triangle-free graphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.