List and correspondence colouring reconfiguration conjectures: optimal diameters $n(G)+\mu(G)$ and $n(G)+\tau(G)$

The reconfiguration graph $\mathcal{C}_L(G)$ has one vertex for each proper colouring of a graph $G$ from a list-assignment $L$ (each vertex $v$ has its own finite list $L(v)$ of allowed colours), with two colourings adjacent when they differ on the colour of a single vertex. When every list satisfies $|L(v)|\ge d(v)+2$, where $d(v)$ is the degree of $v$, this graph is connected, and Cambie, Cames van Batenburg and Cranston conjectured that its diameter is at most $n(G)+\mu(G)$, with $\mu(G)$ the matching number. They conjectured the analogous bound $n(G)+\tau(G)$, with $\tau(G)$ the vertex cover number, for correspondence colourings, where each edge forbids an arbitrary matching of colour pairs between its endpoints' lists. Constructions for every graph show both bounds would be tight, so proofs would determine the exact worst-case reconfiguration diameter in each setting. The problem asks to prove or refute these two conjectures. The best general bounds remain $n+2\mu$ and $n+2\tau$; the conjectures are confirmed when $|L(v)|\ge 2d(v)+1$ and for trees, cactuses, complete bipartite graphs, subcubic graphs (correspondence version), graphs of bounded maximum average degree, and — by later work of de Meyer — subcubic and complete multipartite graphs (list version). Both general conjectures remain open.

Background

Two proper colourings of a graph $G$ can be transformed into one another by recolouring if one is reached from the other by changing the colour of one vertex at a time, keeping the colouring proper after every step. The $k$-colouring reconfiguration graph $\mathcal{C}_k(G)$ has one vertex for each proper $k$-colouring of $G$, and two vertices are adjacent precisely when the corresponding colourings differ on exactly one vertex of $G$; its diameter is the worst-case number of recolouring steps needed between two colourings, and governs the worst-case behaviour of Glauber dynamics, the single-vertex heat-bath Markov chain used for sampling proper colourings. This reconfiguration graph was first defined by Cereceda, van den Heuvel and Johnson, who showed it is connected whenever $k\ge\mathrm{degen}(G)+2$, where the degeneracy $\mathrm{degen}(G)$ is the least $d$ such that every subgraph of $G$ has a vertex of degree at most $d$. The threshold is sharp: a frozen colouring, in which every colour appears on the closed neighbourhood of every vertex, permits no recolouring step at all. Cereceda conjectured that for $n$-vertex $G$ and $k\ge\mathrm{degen}(G)+2$ the diameter of $\mathcal{C}_k(G)$ is $O(n^2)$; this remains open, with the best general bound $O(n^{\mathrm{degen}(G)+1})$ due to Bousquet and Heinrich.

In list colouring each vertex $v$ has its own finite list $L(v)$ of allowed colours, and a proper $L$-colouring assigns $v$ a colour from $L(v)$; ordinary $k$-colouring is the special case of identical lists $\{1,\dots,k\}$. The natural local threshold is $|L(v)|\ge d(v)+2$ for every $v$, where $d(v)$ is the degree of $v$; this guarantees connectivity of the reconfiguration graph $\mathcal{C}_L(G)$ of proper $L$-colourings. Correspondence colouring (also called DP-colouring) generalizes lists further: a correspondence cover $(L,H)$ assigns each vertex a list $L(v)$ and each edge $vw$ a matching between $L(v)$ and $L(w)$, and a proper $(L,H)$-colouring picks one colour per vertex so that the two ends of no edge pick a matched pair; lists are the special case of identity matchings. Write $n(G)$, $\mu(G)$ and $\tau(G)$ for the number of vertices, the matching number (largest set of pairwise disjoint edges), and the vertex cover number (smallest set of vertices meeting every edge); always $\mu(G)\le\tau(G)\le 2\mu(G)$.

Cambie, Cames van Batenburg and Cranston asked for the exact worst-case diameter at the $d(v)+2$ threshold. They conjectured $\mathrm{diam}\,\mathcal{C}_L(G)\le n(G)+\mu(G)$ and $\mathrm{diam}\,\mathcal{C}_{(L,H)}(G)\le n(G)+\tau(G)$, and gave constructions for every graph $G$ showing both bounds would be tight, so a proof of both would fix the exact extremal value in each setting. What is proven in general is the weaker pair of bounds $n(G)+2\mu(G)$ and $n(G)+2\tau(G)$, together with both conjectured bounds under the stronger hypothesis $|L(v)|\ge 2d(v)+1$. Via identical lists with $k\ge\Delta(G)+2$ (where $\Delta(G)$ is the maximum degree), the list conjecture implies $\mathrm{diam}\,\mathcal{C}_k(G)\le n(G)+\mu(G)\le\lfloor 3n/2\rfloor$, the conjectured optimal linear bound in the $k\ge\Delta+2$ regime; combined with the companion lower-bound question $\mathrm{diam}\,\mathcal{C}_k(G)\ge n(G)+\mu(G)$ for $k\ge\Delta(G)+2$ (Question 1 of the source paper, known only for $k\ge 2\Delta(G)$), it would yield $\mathrm{diam}\,\mathcal{C}_k(G)=n(G)+\mu(G)$ and in particular settle the source paper's Regular Cereceda's Conjecture, that $d$-regular graphs at $k=d+2$ satisfy $\mathrm{diam}\,\mathcal{C}_k(G)=n(G)+\mu(G)$.

Problem Statement

Determine whether the following two conjectures of Cambie, Cames van Batenburg and Cranston hold.

(i) List Colouring Reconfiguration Conjecture. For every finite graph $G$ and every list-assignment $L$ such that $|L(v)|\ge d(v)+2$ for every vertex $v\in V(G)$, is $\mathrm{diam}\,\mathcal{C}_L(G)\le n(G)+\mu(G)?$

(ii) Correspondence Colouring Reconfiguration Conjecture. For every finite graph $G$ and every correspondence cover $(L,H)$ such that $|L(v)|\ge d(v)+2$ for every vertex $v\in V(G)$, is $\mathrm{diam}\,\mathcal{C}_{(L,H)}(G)\le n(G)+\tau(G)?$

Here $\mathcal{C}_L(G)$ and $\mathcal{C}_{(L,H)}(G)$ are the reconfiguration graphs of proper $L$-colourings and proper $(L,H)$-colourings respectively, two colourings being adjacent when they differ on exactly one vertex; $n(G)$, $\mu(G)$ and $\tau(G)$ are the number of vertices, the matching number and the vertex cover number; and $d(v)$ is the degree of $v$. Each part is to be settled by a proof in full generality or refuted by an explicit finite counterexample, that is, a graph together with a list-assignment or correspondence cover satisfying the threshold condition and two colourings whose reconfiguration distance exceeds the claimed bound. The two parts form one objective — pinning the exact optimal worst-case diameter at the natural $d(v)+2$ list-size threshold across the colouring hierarchy — and the problem is completely resolved when both parts are settled; since known constructions attain both bounds for every graph, a proof of both parts determines the exact extremal diameter in each setting. Note that neither part implies the other, because $\mu(G)\le\tau(G)\le 2\mu(G)$, although the two share methods.

References

1. Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, "Optimally Reconfiguring List and Correspondence Colourings", European Journal of Combinatorics 115 (2024), article 103798, doi:10.1016/j.ejc.2023.103798, https://arxiv.org/abs/2204.07928
2. Lucas De Meyer, "Optimal list recoloring of subcubic graphs and complete multipartite graphs", Discrete Mathematics 349 (2026), article 115155, doi:10.1016/j.disc.2026.115155, https://arxiv.org/abs/2501.03748
3. Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, "Sharp Bounds on Lengths of Linear Recolouring Sequences", The Electronic Journal of Combinatorics 33(1) (2026), article P1.18, doi:10.37236/13788, https://arxiv.org/abs/2412.19695
4. Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Jan van den Heuvel, Ross J. Kang, "Reconfiguration of List Colourings", arXiv:2505.08020 (2025), https://arxiv.org/abs/2505.08020
5. Nicolas Bousquet, Marc Heinrich, "A polynomial version of Cereceda's conjecture", Journal of Combinatorial Theory, Series B 155 (2022) 1–16, doi:10.1016/j.jctb.2022.01.006
6. Luis Cereceda, Jan van den Heuvel, Matthew Johnson, "Connectedness of the graph of vertex-colourings", Discrete Mathematics 308(5–6) (2008) 913–919, doi:10.1016/j.disc.2007.07.028
7. Carl Feghali, "Reconfiguring colorings of graphs with bounded maximum average degree", Journal of Combinatorial Theory, Series B 147 (2021) 133–138, doi:10.1016/j.jctb.2020.11.001
8. Yichen Wang, Mei Lu, "Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs", Discrete Mathematics 349 (2026), doi:10.1016/j.disc.2026.115055, https://arxiv.org/abs/2509.15456
9. Chenran Pan, Weifan Wang, Runrun Liu, "List Recoloring of Two Classes of Planar Graphs", Graphs and Combinatorics 42 (2026), doi:10.1007/s00373-026-03053-5, https://arxiv.org/abs/2510.17628