Recolouring conjecture for odd-hole-free graphs
Let be an odd-hole-free graph of maximum degree and clique number . A proper colouring is Kempe-recolourable when it can be transformed through Kempe changes, which interchange two colours on a connected component of the corresponding bichromatic subgraph.
Odd-hole-free recolouring conjecture. All odd-hole-free graphs of maximum degree and clique number are -recolourable for
This is motivated by known Kempe-recolouring results for odd-hole-free graphs, which rule out the main known frozen-colouring obstruction above the local Reed threshold. The conjectured full recolourability at this sharper bound 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.