Recolouring conjecture for triangle-free graphs

About 1 year old · traced to

Let GG be a triangle-free graph, let Δ(G)\Delta(G) be its maximum degree, and let kk 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 GG is kk-recolourable for all

k⩾⌈49⋅2+59(Δ(G)+1)⌉.k \geqslant \left\lceil \frac{4}{9}\cdot 2 + \frac{5}{9}(\Delta(G) +1) \right\rceil.

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.

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.