Polynomial Kempe connectivity in degenerate graphs
Polynomial Kempe sequences for degenerate graphs · arXiv:2112.02313
Status open high confidence
The question of whether any two $k$-colorings of a $(k-1)$-degenerate graph on $n$ vertices can always be connected by a Kempe sequence of polynomial length remains open. The source paper (arXiv:2112.02313, published in European Journal of Combinatorics 2023) proves polynomial bounds only under stronger assumptions: $O(kn^2)$ Kempe changes when the graph has treewidth at most $k-1$, and $O(n^2)$ changes when the number of colors equals the maximum degree $\Delta$. No follow-up paper resolving the general $(k-1)$-degenerate case was found in the indexed literature.
Reviewer notes. The source paper partially resolves the question: it proves polynomial bounds for the special cases of bounded treewidth (treewidth at most k-1 gives O(kn^2)) and maximum-degree colorings (O(n^2) for Delta-colorings, with one exception). The open question is specifically about general (k-1)-degenerate graphs with exactly k colors, which subsumes the treewidth case. A related 2025 paper (arXiv:2512.00695) studies Kempe changes in H-free graphs but focuses on Kempe connectivity (existence of a sequence), not polynomial length bounds. No resolution of the full conjecture was found.
Context
Las Vergnas and Meyniel proved in 1981 that all $k$-colorings of a $d$-degenerate graph are Kempe equivalent when $k > d+1$, but their proof yields a sequence that may be exponential in the number of vertices. Whether a polynomial bound can be achieved is posed as an intriguing open question and is the central motivation for all three main results of the paper.
Notes. PDF source — stated as an open question in the abstract and introduction without a labeled environment; no explicit attribution to prior authors.
Source paper
Kempe changes in degenerate graphs
Marthe Bonamy, Vincent Delecroix, Clément Legrand-Duchesne · 2021-12-04
https://arxiv.org/abs/2112.02313
PDF source