Recolouring conjecture for odd-hole-free graphs

About 1 year old · traced to

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.

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

Never refreshed

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.