Recolouring conjecture for triangle-free graphs

From papers

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

k492+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.

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.