Recolouring conjecture for odd-hole-free graphs

From papers

Let GG be an odd-hole-free graph of maximum degree Δ\Delta and clique number ω\omega. 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 Δ\Delta and clique number ω\omega are kk-recolourable for

kω+Δ+12.k \geqslant \left\lceil \frac{\omega + \Delta + 1}{2}\right\rceil.

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

No solutions have been posted yet.