Cereceda's Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite simple graph $G$ is $d$-degenerate if every nonempty subgraph has a vertex of degree at most $d$. A proper $q$-coloring is a map $c:V(G)\to\{1,\ldots,q\}$ whose values differ on adjacent vertices. The reconfiguration graph $\mathcal R_q(G)$ has these proper colorings as vertices; two are adjacent when they differ at exactly one vertex. Its distance counts single-vertex recolorings that preserve propriety at every step.

Statement recorded in the supplied source.

For every fixed integer $d\ge0$, do there exist constants $C_d>0$ and $a_d>0$ such that every $n$-vertex $d$-degenerate graph has \[ \operatorname{diam}\mathcal R_{d+2}(G)\le C_d n^{a_d}? \] The assertion includes connectivity of the reconfiguration graph. [S1][S2] This polynomial formulation is established by the cited bound $O(n^{d+1})$; the stronger customary quadratic bound $O(n^2)$ is a distinct question.

Short English statement

For each fixed degeneracy, can any two proper colorings using two extra colors be joined by a polynomial-length sequence of valid single-vertex recolorings?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1395 (GRAPH-008). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Nicolas Bousquet and Marc Heinrich, A polynomial version of Cereceda's conjecture, Journal of Combinatorial Theory, Series B 155 (2022); arXiv:1903.05619v1, abstract and Section 1. https://arxiv.org/abs/1903.05619v1.