Kempe equivalence of colorings in Kₜ-minor-free graphs

Question 1.7 · arXiv:2103.10684

arXiv Question high confidence— first stated 2025-03-13

Authors: Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne, Jonathan Narboni

Status open medium confidence

Question 1.7 from arXiv:2103.10684 asks whether there exists a constant c' such that for every t, all c'·t-colourings of a K_t-minor-free graph form a single Kempe equivalence class. The paper itself establishes c' ≥ 3/2 if such a constant exists (via Theorem 1.3), while the best known upper bound remains O(t√log t) from the Kostochka–Thomason degeneracy bound combined with Kempe equivalence for degenerate graphs — an O(√log t) factor away from a linear bound. No subsequent paper resolving this gap was found in the indexed literature.

Reviewer notes. Active research on Kempe recolouring by the same group continues (arXiv:2502.10147 treats a recolouring version of Reed's conjecture; arXiv:2512.00695 treats Kempe changes in H-free induced-subgraph-free graphs), but neither paper addresses Question 1.7 directly. The key open gap is whether the O(sqrt(log t)) factor in the upper bound can be eliminated to yield a true linear threshold.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Is there a constant $c^{\prime}$ such that for every $t$, all the $c^{\prime}\cdot t$-colourings of a graph with no $K_{t}$-minor form a single equivalence class?

Context

Theorem 1.3 shows $c'\geqslant\frac{3}{2}$ if such a constant exists. The best known upper bound comes from results of Kostochka and Thomason showing degeneracy $O(t\sqrt{\log t})$ for $K_t$-minor-free graphs, combined with the fact that all $k$-colourings of $d$-degenerate graphs are Kempe equivalent for $k>d$.

Source paper

On a recolouring version of Hadwiger's conjecture
Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne, Jonathan Narboni · 2025-03-13
https://arxiv.org/abs/2103.10684