Recolouring conjecture for odd-hole-free graphs
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.
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.