betaFeedback

WorksMathematics

Large diameter for (Δ+2)(Δ+2)-colouring reconfiguration

Abstract

Given a graph GG and an integer kk, the reconfiguration graph Rk(G)\mathcal{R}_{k}(G) has the proper kk-colourings of GG for vertices, two of which are adjacent if and only if they differ on precisely one vertex of GG. In 20222022, Cambie, Cranston and the author proved that the diameter of RΔ+2(G)\mathcal{R}_{Δ+2}(G) is at most n+2μn+2μ, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of RΔ+2(G)\mathcal{R}_{Δ+2}(G) is precisely equal to n+μn + μ, for every graph GG with nn vertices, matching number μμ and maximum degree ΔΔ. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least n+32μ−2n+\frac{3}{2}μ-2. We also provide counterexamples that are ΔΔ-regular, we show that every graph has reconfiguration diameter at least n+12μn+\frac{1}{2} μ, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.

Introduction

Given a set of objects S\mathcal{S} and a prescribed collection of reversible moves, one can define an associated reconfiguration graph R\mathcal{R}, with vertex set S\mathcal{S}, and two distinct objects adjacent if and only if one can be obtained from the other by a single allowed move. Typically, the moves are chosen to reflect a small local modification of the object, so that the distance in R\mathcal{R} between s,t∈Ss,t\in\mathcal{S} is a good measure for how closely related ss and tt are. More precisely, reconfiguration graphs form a model for how easily two objects can be converted into each other via a sequence of (small) changes, while staying inside the space of relevant objects.

In the classic example, S\mathcal{S} is the set of configurations of a Rubik’s cube, and the allowed moves are the turns of the cube. Then the diameter of R\mathcal{R} is the maximum number of turns required to convert any two given configurations into each other. In particular, this upper bounds the maximum number of moves needed to solve any Rubik’s cube. In more serious situations, S\mathcal{S} may represent the possible states of a physical, chemical or biological system. We refer to the surveys [34, 30] for various other examples.

In one of the most well-studied settings, S\mathcal{S} is the set of proper kk-vertex-colourings of some fixed graph GG, for some positive integer kk. Under the canonical reconfiguration rule, two kk-colourings c1,c2c_1,c_2 are adjacent if and only if they differ on precisely one vertex of GG. From now on we only consider this type of reconfiguration graph, and we denote it by Rk(G)\mathcal{R}_k(G).

Connectivity and the diameter of Rk(G)\mathcal{R}_k(G) have been studied in relation to various graph parameters and structural restrictions, including degeneracy [24, 14, 12], maximum average degree [27, 21 ZL26], bipartite graphs [17, 1], treewidth [2, 3, 5, 36], excluded minors [GLL+26], planar graphs [DF21, BBF+23, CM24, Cra25, DL26], and excluded induced subgraphs (especially for kk equal to one plus the chromatic number) [13, 3, 7, 8 LMM+24, 9 BCS26]. In this current work, we focus on the maximum degree [31, 28, 6, 15, 11, 16, 26].

Let Δ=Δ(G)\Delta= \Delta(G) and n=n(G)n = n(G) denote the maximum degree and number of vertices of GG, respectively. Complete graphs show that Rk(G)\mathcal{R}_k(G) can be empty or disconnected when k≤Δ+1k \le\Delta+ 1. However, it is connected (and hence has finite diameter) whenever k≥Δ+2k \ge\Delta+ 2. In this range, Jerrum [31] in fact gave an argument that implies an exponential upper bound 2O(n)2^{O(n)} on the diameter. Cereceda [18] subsequently improved this to O(nΔ)O(n\Delta), and hence O(n2)O(n^2). Finally, Cambie, the author, and Cranston [15] showed that the diameter is linear in nn, namely at most 2n−12n - 1.

This is close to optimal: by relabelling colours one obtains two colourings that differ at every vertex, so for every graph GG the diameter of RΔ+2(G)\mathcal{R}_{\Delta+2}(G) must be at least nn. Inspired by the fact that diam⁡RΔ+2(Kn)=⌊3n2⌋\operatorname{diam}\mathcal{R}_{\Delta+2}(K_n) = \left\lfloor\frac{3n}{2} \right\rfloor for complete graphs KnK_n, and via the intermediate Conjecture 19 mentioned at the end of this manuscript, three refined conjectures on the exact value of the diameter were formulated. Recall that the matching number μ=μ(G)\mu= \mu(G) of a graph GG is the maximum number of vertex-disjoint edges and the vertex cover number τ=τ(G)\tau= \tau(G) is the smallest size of a vertex set that contains at least one endpoint of every edge. The inequality μ(G)≤τ(G)\mu(G) \le\tau(G) holds for every graph, with equality for bipartite graphs due to König’s Theorem.

Conjecture 1. [15] For every graph GG with nn vertices, maximum degree Δ\Delta, matching number μ\mu and vertex cover number τ\tau,

(i) diam⁡RΔ+2(G)≤n+τ\operatorname{diam}\mathcal{R}_{\Delta+2}(G) \le n + \tau;

(ii) diam⁡RΔ+2(G)≤n+μ\operatorname{diam}\mathcal{R}_{\Delta+2}(G) \le n + \mu;

(iii) diam⁡RΔ+2(G)=n+μ\operatorname{diam}\mathcal{R}_{\Delta+2}(G) = n + \mu if GG is regular.

On the lower bound side, it was also asked in [15] whether diam⁡RΔ+2(G)≥n+μ\operatorname{diam}\mathcal{R}_{\Delta+2}(G) \ge n + \mu for every graph GG. This suggested the tantalizingly beautiful possibility of equality diam⁡Rk(G)=n+μ\operatorname{diam}\mathcal{R}_k(G) = n + \mu for every graph GG and k≥Δ+2k \ge\Delta+ 2. The following proposition gives a nonexhaustive selection of evidence from the literature that was gathered in support of this, and Conjecture 1 in particular.

Proposition 2. [15, 26, 37] For every graph GG with nn vertices, maximum degree Δ≥1\Delta\ge1 and matching number μ\mu,

(i) diam⁡Rk(G)=n+μ\operatorname{diam}\mathcal{R}_k(G) = n + \mu for all k≥2Δ+1k \ge2\Delta+ 1;

(ii) diam⁡Rk(G)≤n+2μ\operatorname{diam}\mathcal{R}_k(G) \le n + 2\mu for all k≥Δ+2k \ge\Delta+ 2;

(iii) diam⁡Rk(G)≥n+μ\operatorname{diam}\mathcal{R}_k(G) \ge n + \mu for all k≥Δ+2k \ge\Delta+ 2, provided GG is bipartite;

(iv) diam⁡Rk(G)=n+μ\operatorname{diam}\mathcal{R}_k(G) = n + \mu for all k≥Δ+2k \ge\Delta+ 2, provided Δ≤3\Delta\le3 or GG is complete multipartite or a tree.

Counterexamples

Conjectures 1.(i) and 1.(ii) are special cases of the Correspondence Colouring Reconfiguration Conjecture and the List Colouring Reconfiguration Conjecture, respectively, and Conjecture 1.(iii) was called the Regular Cereceda Conjecture in [15]. We disprove all of them via Theorems 3 and 4 below.

Theorem 3. For every integer t≥2t \ge2, there is a graph GG with n(G)=t2n(G) = t^2 vertices, maximum degree Δ(G)=2t−2\Delta(G) = 2t - 2 and matching number and vertex cover number τ(G)=μ(G)=t\tau(G) = \mu(G) = t, such that

diam⁡RΔ(G)+2(G)≥n(G)+32μ(G)−2.\operatorname{diam}\mathcal{R}_{\Delta(G)+2}(G) \ge n(G) + \frac{3}{2}\mu(G) - 2.

Theorem 4. There exist 8-regular graphs GG such that diam⁡R10(G)≥n(G)+166165μ(G)\operatorname{diam} R_{10}(G) \ge n(G) + \frac{166}{165}\mu(G). Moreover, for all even Δ≥8\Delta\ge8 there exists a Δ\Delta-regular graph GG such that

diam⁡RΔ+2(G)>n(G)+μ(G).\operatorname{diam} R_{\Delta+2}(G) > n(G) + \mu(G).

Additional results

Each graph constructed in the proof of Theorem 3 is the 1-subdivision of a multigraph. Therefore they are bipartite, such that all vertices in one of the two parts have degree 2. The following converse theorem shows that the factor 3/23/2 is the asymptotically optimal coefficient of μ\mu within that class of bipartite graphs.

Theorem 5. Let GG be a bipartite graph such that all vertices in one of the parts have degree at most 2. If k=Δ(G)+2k = \Delta(G) + 2, then

diam⁡Rk(G)≤n(G)+32μ(G).\operatorname{diam} R_k(G) \le n(G) + \frac{3}{2}\mu(G).

If k≥Δ(G)+3k \ge\Delta(G) + 3, then

diam⁡Rk(G)=n(G)+μ(G).\operatorname{diam} R_k(G) = n(G) + \mu(G).

We complement this with a simple bound for bipartite graphs in terms of only the number of vertices, which appears to have eluded explicit statement in the literature. It is sharp due to balanced complete bipartite graphs.

Lemma 6. Let GG be a bipartite graph. If k≥Δ(G)+2k \ge\Delta(G) + 2, then diam⁡Rk(G)≤32n(G)\operatorname{diam} R_k(G) \le\frac{3}{2}n(G).

Finally, we provide a lower bound that is valid for all graphs.

Theorem 7. Let GG be a graph. If k≥Δ(G)+2k \ge\Delta(G) + 2, then

diam⁡Rk(G)≥n(G)+12μ(G).\operatorname{diam} R_k(G) \ge n(G) + \frac{1}{2}\mu(G).

In a different direction, we present an extension to hypergraphs H\mathcal{H}, showing that in that setting the diameter of the reconfiguration graph is linear in the number of vertices as well. The exact value of the diameter may be more elusive than for graphs, even when the number of colours is large. We refer to § 6 for the relevant definitions and two illustrative corollaries concerning acyclic colourings and partitions into induced forests.

Lemma 8. Let H\mathcal{H} be a loopless hypergraph on nn vertices and let k≥Δ∗(H)+2k \ge\Delta^*(\mathcal{H}) + 2. Then

n≤diam⁡Rk(H)≤2n.n \le\operatorname{diam} R_k(\mathcal{H}) \le2n.

Organization

The main result Theorem 3 is proved in § 2. After that, in Section 3 we modify the construction to obtain regular graphs that certify Theorem 4. In the remaining sections we prove Lemmas 6 and 8 and stronger forms of Theorem 5 and Theorem 7. We end with a number of open problems.

Highly nonregular counterexamples

In this section, we prove Theorem 3: for every μ≥2\mu\ge2 there exists a graph GμG_\mu on nn vertices with matching number μ\mu and maximum degree Δ\Delta such that the reconfiguration graph of proper (Δ+2)(\Delta+ 2)-colourings of GμG_\mu has diameter at least n+3μ2−2n + \frac{3\mu}{2} - 2. The construction is a subdivision of a complete multigraph. See Figure 1 for an illustration of G3G_3.

Figure 1. The graph G3G_3 with the colourings α\alpha (left) and β\beta (right).

We now give the details.

Proof of Theorem 3. For t≥2t \ge2, let GtG_t be the bipartite graph with parts

X={x1,…,xt}andY={yij:1≤i,j≤t, i≠j},X = \{x_1,\ldots,x_t\} \quad\text{and}\quad Y = \{y_{ij}: 1 \le i,j \le t,\ i \ne j\},

where the neighbourhood of yijy_{ij} is {xi,xj}\{x_i,x_j\}, for every i≠ji \ne j. Thus GtG_t is obtained by subdividing once every edge of the multigraph formed by doubling each edge of the complete graph KtK_t. The number of vertices, maximum degree, matching number and vertex cover number of GtG_t are

n(Gt)=t2,Δ(Gt)=2t−2,μ(Gt)=τ(Gt)=t.n(G_t)=t^2,\qquad\Delta(G_t)=2t-2,\qquad\mu(G_t)=\tau(G_t)=t.

Indeed, XX is a vertex cover so that μ(Gt)≤τ(Gt)≤t\mu(G_t) \le\tau(G_t) \le t, and the edges xiyi,i+1x_i y_{i,i+1} (with indices modulo tt) form a matching so that t≤μ(Gt)t \le\mu(G_t). We now define two 2t2t-colourings α\alpha and β\beta, and we will show that they are at distance at least n(Gt)+32μ(Gt)−2n(G_t)+\frac{3}{2}\mu(G_t)-2. Use 2t2t distinct colours a1,…,at,b1,…,bta_1,\ldots,a_t,b_1,\ldots,b_t, and define α\alpha and β\beta by

α\alphaβ\beta
xix_iaia_ibib_i
yijy_{ij}bib_iaja_j

The restrictions of these colourings to the subgraph induced by {xi,yij,yji,xj}\{x_i,y_{ij},y_{ji},x_j\} are shown in Figure 2, and the colourings of G3G_3 are illustrated in Figure 1.

Figure 2. The two colourings α\alpha (left) and β\beta (right) restricted to the induced subgraph Gt[{xi,yij,yji,xj}]≅G2G_t[\{x_i,y_{ij},y_{ji},x_j\}] \cong G_2.

Both colourings α\alpha and β\beta are proper, and they differ at every vertex. Therefore every vertex will have to be recoloured at least once, requiring at least t2t^2 recolourings. Consider any shortest recolouring sequence from α\alpha to β\beta, and write its length as t2+rt^2+r, where rr counts recolourings beyond the first at each vertex. Call a vertex repeated if it is recoloured at least twice.

Claim 1. If xix_i is recoloured exactly twice, then it has a repeated neighbour in YY.

Proof. Suppose xix_i is recoloured exactly twice, following ai→c→bia_i \to c \to b_i for some c∈{ai,bi}c \in\{a_i,b_i\}. If c=bjc=b_j for some j≠ij \ne i, then yjiy_{ji} must leave bjb_j before xix_i leaves aia_i. Its first recolouring therefore cannot be directly to its target colour aia_i, so yjiy_{ji} is repeated. If c=ajc=a_j for some j≠ij \ne i, suppose that yijy_{ij} is not repeated. Its unique recolouring must then be from bib_i to aja_j. This cannot occur before xix_i gets colour aja_j, as it would block that recolouring. It also cannot occur while xix_i has colour aja_j, as this would violate properness. It also cannot occur after xix_i is coloured bib_i, as yijy_{ij} would still have colour bib_i at that time. Thus yijy_{ij} is repeated. ◇

Claim 2. If i≠ji \ne j and xi,xjx_i,x_j are both recoloured exactly once, then at least one of yij,yjiy_{ij},y_{ji} is repeated.

Proof. Suppose that neither yijy_{ij} nor yjiy_{ji} is repeated. Then each is recoloured exactly once. Writing u≺vu \prec v when the unique recolouring of uu precedes the unique recolouring of vv, properness requires xj≺yij≺xix_j \prec y_{ij} \prec x_i and xi≺yji≺xjx_i \prec y_{ji} \prec x_j. These chronological orders are incompatible. Hence at least one of yij,yjiy_{ij},y_{ji} is repeated. ◇

Let X1,X2,X3X_1,X_2,X_3 denote the disjoint sets of XX-vertices that are recoloured once, twice, and at least three times, respectively, so ∣X1∣+∣X2∣+∣X3∣=t|X_1|+|X_2|+|X_3|=t. Let yy be the number of repeated YY-vertices. Then

r≥∣X2∣+2∣X3∣+y.r \ge|X_2|+2|X_3|+y.

By Claim 2, there are at least (∣X1∣2)\binom{|X_1|}{2} repeated YY-vertices whose endpoints are both in X1X_1. Disjoint from that, by Claim 1, there are at least ∣X2∣/2|X_2|/2 repeated YY-vertices adjacent to some vertex of X2X_2, where the division by 2 is because an YY-vertex could be adjacent to two vertices from X2X_2. Hence

y≥(∣X1∣2)+∣X2∣2.y \ge\binom{|X_1|}{2}+\frac{|X_2|}{2}.

Therefore 2r≥3∣X2∣+4∣X3∣+∣X1∣2−∣X1∣=3t−4+(∣X1∣−2)2+∣X3∣≥3t−42r \ge3|X_2|+4|X_3|+|X_1|^2-|X_1|=3t-4+(|X_1|-2)^2+|X_3|\ge3t-4. It follows that the diameter of R2t(Gt)\mathcal{R}_{2t}(G_t) is at least

dist⁡R2t(Gt)(α,β)=t2+r≥t2+3t−42=n(Gt)+3μ(Gt)2−2.\operatorname{dist}_{\mathcal{R}_{2t}(G_t)}(\alpha,\beta)=t^2+r\ge t^2+\frac{3t-4}{2}=n(G_t)+\frac{3\mu(G_t)}{2}-2.

Theorem 9. For every even Δ\Delta, there exists a Δ\Delta-regular graph HH such that

diam⁡RΔ+2(H)≥n(H)+μ(H)+⌊Δ−44⌋.\operatorname{diam}\mathcal{R}_{\Delta+2}(H)\ge n(H)+\mu(H)+\left\lfloor\frac{\Delta-4}{4}\right\rfloor.

Proof. Fix an even Δ≥2\Delta\ge2, put t=Δ/2+1t=\Delta/2+1 and m=t(t−1)m=t(t-1), and take the graph GtG_t with parts X,YX,Y and colourings α,β\alpha,\beta that were constructed in the proof of Theorem 3. Thus ∣Y∣=m|Y|=m, every xix_i has degree Δ\Delta, and every yijy_{ij} has degree two.

Let BB be obtained from the complete bipartite graph KΔ,ΔK_{\Delta,\Delta} by deleting a matching of size (Δ−2)/2(\Delta-2)/2. Exactly Δ−2\Delta-2 vertices of BB have degree Δ−1\Delta-1, and the remaining vertices have degree Δ\Delta. Moreover, note that n(B)=2Δn(B)=2\Delta and BB has a perfect matching so that μ(B)=Δ\mu(B)=\Delta. For each i≠ji\ne j,

@page 5/15 starts_mid=1 ends_mid=1

Theorem 9. For every even Δ\Delta, there exists a Δ\Delta-regular graph HH such that

diam⁡RΔ+2(H)≥n(H)+μ(H)+⌊Δ−44⌋.\operatorname{diam}\mathcal{R}_{\Delta+2}(H)\ge n(H)+\mu(H)+\left\lfloor\frac{\Delta-4}{4}\right\rfloor.

Proof. Fix an even Δ≥2\Delta\ge2, put t=Δ/2+1t=\Delta/2+1 and m=t(t−1)m=t(t-1), and take the graph GtG_t with parts X,YX,Y and colourings α,β\alpha,\beta that were constructed in the proof of Theorem 3. Thus ∣Y∣=m|Y|=m, every xix_i has degree Δ\Delta, and every yijy_{ij} has degree two.

Let BB be obtained from the complete bipartite graph KΔ,ΔK_{\Delta,\Delta} by deleting a matching of size (Δ−2)/2(\Delta-2)/2. Exactly Δ−2\Delta-2 vertices of BB have degree Δ−1\Delta-1, and the remaining vertices have degree Δ\Delta. Moreover, note that n(B)=2Δn(B)=2\Delta and BB has a perfect matching so that μ(B)=Δ\mu(B)=\Delta. For each i≠ji\ne j, take a disjoint copy BijB_{ij} of BB and join its Δ−2\Delta-2 degree-(Δ−1)(\Delta-1) vertices to yijy_{ij}. The resulting graph HtH_t is Δ\Delta-regular, and

n(Ht)=t2+2Δm,μ(Ht)=t+Δm.n(H_t)=t^2+2\Delta m,\qquad\mu(H_t)=t+\Delta m.

For the matching-number lower bound, combine a maximum matching of GtG_t with a perfect matching in each BijB_{ij}. Conversely, a matching uses at most one edge between yijy_{ij} and BijB_{ij} for each i≠ji\ne j. If it uses one, then at most Δ−1\Delta-1 edges remain inside BijB_{ij}, and otherwise at most Δ\Delta. Thus any given matching has at most Δ\Delta edges with an endpoint in BijB_{ij}, for every i≠ji\ne j, and at most μ(Gt)=t\mu(G_t)=t further edges lie in GtG_t.

Next we lower bound the diameter of the reconfiguration graph of HtH_t. Extend α,β\alpha,\beta to HtH_t using the same palette {a1,…,at,b1,…,bt}\{a_1,\ldots,a_t,b_1,\ldots,b_t\} of 2t=Δ+22t=\Delta+2 colours that was used for GtG_t. In each BijB_{ij}, choose two distinct colours cij,dijc_{ij},d_{ij} outside {bi,aj}\{b_i,a_j\}, colour its two parts cij,dijc_{ij},d_{ij} in α\alpha, and interchange these colours in β\beta. Both extensions are proper, since α(yij)=bi\alpha(y_{ij})=b_i and β(yij)=aj\beta(y_{ij})=a_j.

Consider any recolouring sequence between these extensions. Its restriction to GtG_t requires at least t2+⌈3t/2⌉−2t^2+\lceil3t/2\rceil-2 recolourings, by the proof of Theorem 3 and integrality. In each BijB_{ij}, every vertex must be recoloured, and the colours on each edge of a perfect matching are interchanged. At least one endpoint of each such edge must therefore be recoloured twice. Hence each copy requires at least 3Δ3\Delta recolourings. These vertex sets are disjoint, so

diam⁡RΔ+2(Ht)≥t2+⌈3t2⌉−2+3Δm=n(Ht)+μ(Ht)+⌈t2⌉−2=n(Ht)+μ(Ht)+⌊Δ−44⌋.\operatorname{diam}\mathcal{R}_{\Delta+2}(H_t)\ge t^2+\left\lceil\frac{3t}{2}\right\rceil-2+3\Delta m=n(H_t)+\mu(H_t)+\left\lceil\frac{t}{2}\right\rceil-2=n(H_t)+\mu(H_t)+\left\lfloor\frac{\Delta-4}{4}\right\rfloor.

Corollary 10. There exist infinitely many 88-regular graphs HH with diam⁡R10(H)≥n(H)+166165μ(H)\operatorname{diam}\mathcal{R}_{10}(H)\ge n(H)+\frac{166}{165}\mu(H).

Proof. The construction in the proof of Theorem 9 yields an 88-regular graph H5H_5 with matching number 5+8⋅20=1655+8\cdot20=165, such that diam⁡R10(H5)≥n(H5)+μ(H5)+1\operatorname{diam}\mathcal{R}_{10}(H_5)\ge n(H_5)+\mu(H_5)+1. Now take rr disjoint copies of H5H_5. The resulting graph HH satisfies diam⁡R10(H)≥r⋅(n(H5)+μ(H5)+1)=r⋅(n(H5)+166165μ(H5))=n(H)+166165μ(H)\operatorname{diam}\mathcal{R}_{10}(H)\ge r\cdot(n(H_5)+\mu(H_5)+1)=r\cdot(n(H_5)+\frac{166}{165}\mu(H_5))=n(H)+\frac{166}{165}\mu(H).

We remark that the construction and computation of Corollary 10 generalizes to all even Δ\Delta. For every even integer Δ≥4\Delta\ge4, there exist infinitely many Δ\Delta-regular graphs HH such that diam⁡RΔ+2(H)≥n(H)+(1+4⌊(Δ−4)/4⌋(Δ+2)(Δ2+2))μ(H)\operatorname{diam}\mathcal{R}_{\Delta+2}(H)\ge n(H)+(1+\frac{4\lfloor(\Delta-4)/4\rfloor}{(\Delta+2)(\Delta^2+2)})\mu(H). Furthermore, we elected to give the simplest construction and proof for Theorem 9, by using the gadget BB obtained from KΔ,ΔK_{\Delta,\Delta} minus a matching. With other choices it is possible to do slightly better. For instance, Theorem 9 also holds with B=KΔ+2−(CΔ−2∪2K2)B=K_{\Delta+2}-(C_{\Delta-2}\cup2K_2), a complete graph minus the disjoint union of a cycle of length Δ−2\Delta-2 and two edges. Since the resulting Δ\Delta-regular graph HH is smaller, for Δ=8\Delta=8 the analogue of Corollary 10 then gives a better bound diam⁡R10(H)≥n(H)+101105μ(H)\operatorname{diam}\mathcal{R}_{10}(H)\ge n(H)+\frac{101}{105}\mu(H).

Bipartite graphs with degree at most two on one side

In this section we prove Theorem 5. The lower bound directly follows from [15 Proposition 3]: diam⁡Rk(G)≥n(G)+μ(G)\operatorname{diam}\mathcal{R}_k(G)\ge n(G)+\mu(G) for every bipartite graph GG and every k≥3k\ge3. Therefore we only need to prove upper bounds, which we will do in a stronger form to facilitate induction. Given a graph GG and a list-assignment L:V(G)→2NL:V(G)\to2^{\mathbb{N}}, an LL-colouring (or list colouring) is a proper vertex colouring c:V(G)→Nc:V(G)\to\mathbb{N} such that c(v)∈L(v)c(v)\in L(v) for every vertex vv. The LL-colouring reconfiguration graph RL(G)\mathcal{R}_L(G) of a graph GG has as vertices the LL-colourings of GG, two of which are adjacent if they differ on precisely one vertex of GG. Since kk-colourings (for k∈Nk\in\mathbb{N}) are special cases of list colourings, the following implies the upper bounds in Theorem 5.

Theorem 11. Let GG be bipartite with bipartition A∪BA \cup B, where deg⁡(b)≤2\deg(b) \le2 for every b∈Bb \in B.

  1. If ∣L(v)∣≥deg⁡(v)+2|L(v)| \ge\deg(v) + 2 for every vertex vv, then diam⁡RL(G)≤n(G)+32μ(G)\operatorname{diam}\mathcal{R}_L(G) \le n(G) + \frac{3}{2}\mu(G).

  1. If ∣L(a)∣≥deg⁡(a)+3|L(a)| \ge\deg(a) + 3 for every a∈Aa \in A and ∣L(b)∣≥deg⁡(b)+2|L(b)| \ge\deg(b) + 2 for every b∈Bb \in B, then diam⁡RL(G)≤n(G)+μ(G)\operatorname{diam}\mathcal{R}_L(G) \le n(G) + \mu(G).

Proof. Fix one of the two statements, and let λ∈{32,1}\lambda\in\{\frac{3}{2},1\} be its coefficient of μ(G)\mu(G). Suppose that it is false, and choose a counterexample of minimum order, with LL-colourings α,β\alpha,\beta at distance greater than n+λμn+\lambda\mu, where n=n(G)n=n(G) and μ=μ(G)\mu=\mu(G). The cases n≤1n\le1 are immediate.

We repeatedly use the following observation. If some recolourings of α\alpha and β\beta make them agree on a set SS, using rr recolouring steps in total, we may fix and delete SS, removing its colours from the lists of its remaining neighbours. The conditions on the list sizes are preserved, since each remaining vertex loses at most one colour for each deleted neighbour. Minimality therefore gives

dist⁡RL(G)(α,β)≤r+n−∣S∣+λ⋅μ(G−S).(1)\operatorname{dist}_{\mathcal{R}_L(G)}(\alpha,\beta) \le r+n-|S|+\lambda\cdot\mu(G-S). \tag*{(1)}

Let DD be the digraph with an arc u→vu\to v whenever uv∈E(G)uv\in E(G) and β(u)=α(v)\beta(u)=\alpha(v). (Note that an arc u→vu\to v means that the current colour α(v)\alpha(v) of vv blocks uu from being directly recoloured to its target colour β(u)\beta(u).) We claim that DD is strongly connected. Otherwise, choose a nonempty proper subset X⊂V(G)X\subset V(G) with no outgoing arc. First recolour G[X]G[X] from α\alpha to β\beta without recolouring any vertex of G−XG-X (this is possible because there is no arc from XX to G−XG-X). Subsequently recolour G−XG-X from α\alpha to β\beta.

Since μ(G[X])+μ(G−X)≤μ(G)\mu(G[X])+\mu(G-X)\le\mu(G), applying inequality (1) to S=XS=X and to S=G−XS=G-X gives a sequence of length at most n+λμn+\lambda\mu, a contradiction. Thus DD is strongly connected. In particular, GG is connected and α(v)≠β(v)\alpha(v)\ne\beta(v) for every vertex.

If GG is a tree, then diam⁡(RL(G))≤n(G)+μ(G)\operatorname{diam}(\mathcal{R}_L(G))\le n(G)+\mu(G) follows from [15 Corollary 18]. We may therefore assume that GG contains a cycle. In this case μ=∣A∣\mu=|A|. Since AA is one part of the bipartition, the inequality μ≤∣A∣\mu\le|A| is immediate. For the reverse inequality, take a spanning unicyclic subgraph, orient its cycle cyclically, and orient all remaining edges away from the cycle. Every vertex has indegree one, while every vertex of BB has outdegree at most one. The edges directed into AA therefore form a matching saturating AA.

If for some a∈Aa\in A there is a colour c∈L(a)c\in L(a) absent from both α(N(a))\alpha(N(a)) and β(N(a))\beta(N(a)), then recolour vertex aa to cc with respect to both α\alpha and β\beta. This requires two recolouring steps in total. Since μ(G−a)≤∣A∣−1=μ−1\mu(G-a)\le|A|-1=\mu-1, inequality (1) applied to S={a}S=\{a\} yields dist⁡RL(G)(α,β)≤2+n−1+λ⋅(μ−1)≤n+λ⋅μ\operatorname{dist}_{\mathcal{R}_L(G)}(\alpha,\beta)\le2+n-1+\lambda\cdot(\mu-1)\le n+\lambda\cdot\mu, a contradiction. Hence

L(a)⊆α(N(a))∪β(N(a))for every a∈A.L(a)\subseteq\alpha(N(a))\cup\beta(N(a)) \qquad\text{for every }a\in A.

Let f(v)=deg⁡D+(v)+deg⁡D−(v)f(v)=\deg_D^+(v)+\deg_D^-(v) denote the number of arcs incident to vv. The multiset M(a):=α(N(a))∪β(N(a))M(a):=\alpha(N(a))\cup\beta(N(a)) contains 2deg⁡(a)2\deg(a) colours (counted with multiplicity) appearing in the neighbourhood of aa. Among them, exactly f(a)f(a) have colour α(a)\alpha(a) or β(a)\beta(a), and both colours occur by strong connectivity. So the number of distinct colours ∣M(a)∣|M(a)| in M(a)M(a) is at most 2deg⁡(a)−(deg⁡D+(a)−1)−(deg⁡D−(a)−1)=2deg⁡(a)−f(a)+22\deg(a)-(\deg_D^+(a)-1)-(\deg_D^-(a)-1)=2\deg(a)-f(a)+2. Thus,

deg⁡(a)+2≤∣L(a)∣≤∣M(a)∣≤2deg⁡(a)−f(a)+2,\deg(a)+2\le|L(a)|\le|M(a)|\le2\deg(a)-f(a)+2,

so f(a)≤deg⁡(a)f(a)\le\deg(a). Since every vertex of DD has positive indegree and outdegree,

2∣B∣≤∑b∈Bf(b)=∑a∈Af(a)≤∑a∈Adeg⁡(a)=∑b∈Bdeg⁡(b)≤2∣B∣.2|B|\le\sum_{b\in B}f(b)=\sum_{a\in A}f(a)\le\sum_{a\in A}\deg(a)=\sum_{b\in B}\deg(b)\le2|B|.

All inequalities must be equalities. In particular, f(a)=deg⁡(a)f(a) = \deg(a) and ∣L(a)∣=deg⁡(a)+2|L(a)| = \deg(a) + 2 for every a∈Aa \in A. This contradicts the statement for λ=1\lambda= 1, proving the second list-colouring statement.

It remains to finish the case λ=32\lambda= \frac{3}{2}. The equality conditions imply that every b∈Bb \in B has degree two and exactly one incoming and one outgoing arc in DD. They also imply that for every vertex a∈Aa \in A we have L(a)=M(a)L(a) = M(a) (viewed as a set), and every colour in L(a)∖{α(a),β(a)}L(a) \setminus\{\alpha(a), \beta(a)\} occurs exactly once in the multiset M(a)M(a).

Since DD is strongly connected and ∣A∣≥2|A| \ge2, it contains a directed path u→b→vu \to b \to v with distinct u,v∈Au, v \in A. Write

x=α(b)=β(u),y=β(b)=α(v).x = \alpha(b) = \beta(u), \qquad y = \beta(b) = \alpha(v).

The unique incoming and outgoing arcs at bb imply that

y∉{α(u),β(u)},x∉{α(v),β(v)}.y \notin\{\alpha(u), \beta(u)\}, \qquad x \notin\{\alpha(v), \beta(v)\}.

Consequently, y∈L(u)y \in L(u) and it has a unique occurrence in the multiset M(u)M(u), namely β(b)=y\beta(b) = y. In particular, y∉α(N(u))y \notin\alpha(N(u)). Similarly, x∈L(v)x \in L(v) and it has a unique occurrence in the multiset M(v)M(v), namely α(b)=x\alpha(b) = x. In particular, x∉β(N(v))x \notin\beta(N(v)).

We now choose some free colour z∈L(b)∖{x,y}z \in L(b) \setminus\{x,y\} and perform the following six recolourings (three starting from α\alpha and three starting from β\beta), in the indicated order:

starting colouringfirstsecondthird
α\alphau←yu \leftarrow yb←zb \leftarrow zv←xv \leftarrow x
β\betav←xv \leftarrow xb←zb \leftarrow zu←yu \leftarrow y

Table 1.

The uniqueness properties just established, in particular y∉α(N(u))y \notin\alpha(N(u)) and x∉β(N(v))x \notin\beta(N(v)), ensure the recolourings at uu and vv are allowed. Immediately before the recolouring of bb, its two neighbours both have colour yy in the first row and colour xx in the second, so that recolouring is possible as well. The resulting colourings agree on S={u,b,v}S = \{u,b,v\}, and μ(G−S)≤∣A∣−2=μ−2\mu(G-S) \le|A| - 2 = \mu- 2. Applying (1), we obtain the final contradiction dist⁡RL(G)(α,β)≤6+n−3+32(μ−2)=n+32μ\operatorname{dist}_{R_L(G)}(\alpha,\beta) \le6 + n - 3 + \frac{3}{2}(\mu- 2) = n + \frac{3}{2}\mu.

A sharp upper bound for bipartite graphs

In this section we prove Lemma 6. We restate it for convenience.

Lemma 12. If GG is bipartite and k≥Δ(G)+2k \ge\Delta(G) + 2, then diam⁡Rk(G)≤32n(G)\operatorname{diam} R_k(G) \le\frac{3}{2}n(G).

Proof. Fix two proper kk-colourings α,β\alpha,\beta and a bipartition V(G)=A⊔BV(G) = A \sqcup B. Choose any colour c∈[k]c \in[k]. For X∈{A,B}X \in\{A,B\} put

mX(c)=∣α−1(c)∩X∣+∣β−1(c)∩X∣.m_X(c) = |\alpha^{-1}(c) \cap X| + |\beta^{-1}(c) \cap X|.

Starting from either colouring γ∈{α,β}\gamma\in\{\alpha,\beta\}, first recolour every vertex vv of BB currently coloured cc to a different available colour. This is possible because at most dG(v)+1d_G(v) + 1 colours are forbidden by the current neighbours and the old colour cc. Since BB is independent, these recolouring steps do not interfere with each other. Next, recolour every vertex of AA not already coloured cc to $c. This is allowed because BB no longer uses cc, and AA is independent. The number of recolourings starting from γ\gamma is at most

∣γ−1(c)∩B∣+∣A∣−∣γ−1(c)∩A∣.|\gamma^{-1}(c) \cap B| + |A| - |\gamma^{-1}(c) \cap A|.

The two resulting colourings agree on AA, which is monochromatic in colour cc. Join them by recolouring each vertex of BB at most once, while keeping AA fixed, and then reverse the sequence constructed from β\beta. This gives an α\alpha–β\beta recolouring sequence of length at most ℓA=2∣A∣+∣B∣+mB(c)−mA(c)\ell_A = 2|A| + |B| + m_B(c) - m_A(c). Interchanging AA and BB gives another such recolouring sequence of length at most ℓB=∣A∣+2∣B∣+mA(c)−mB(c)\ell_B = |A| + 2|B| + m_A(c) - m_B(c). Both constructions use the same arbitrarily chosen colour cc. Since ℓA+ℓB=3(∣A∣+∣B∣)=3n\ell_A + \ell_B = 3(|A| + |B|) = 3n, we obtain dist⁡Rk(G)(α,β)≤min⁡{ℓA,ℓB}≤⌊3n2⌋\operatorname{dist}_{\mathcal{R}_k(G)}(\alpha,\beta) \le\min\{\ell_A,\ell_B\} \le\left\lfloor\frac{3n}{2} \right\rfloor.

Corollary 13. If GG is bipartite and has a perfect matching, then for every k≥Δ(G)+2k \ge\Delta(G) + 2, diam⁡Rk(G)=n(G)+μ(G)=⌊32n(G)⌋\operatorname{diam}\mathcal{R}_k(G) = n(G) + \mu(G) = \left\lfloor\frac{3}{2}n(G) \right\rfloor.

Proof. Take the two colourings obtained by interchanging colours 1 and 2 on the bipartition classes. Every vertex must be recoloured, and for each edge of a maximum matching at least one endpoint must be recoloured twice. This gives the lower bound n(G)+μ(G)=⌊32n(G)⌋n(G) + \mu(G) = \left\lfloor\frac{3}{2}n(G) \right\rfloor and Lemma 6 gives the upper bound.

A general lower bound

This section contains the proof of Theorem 7 in a slightly stronger form, namely Theorem 14 below. For k≥2Δk \ge2\Delta, it recovers the known lower bound n+μn + \mu on the diameter. For k=Δ+2≥4k = \Delta+ 2 \ge4, it implies diam⁡RΔ+2(G)≥n+⌊Δ/2⌋+1Δμ\operatorname{diam}\mathcal{R}_{\Delta+2}(G) \ge n + \frac{\lfloor\Delta/2 \rfloor+ 1}{\Delta}\mu, which is strictly larger than n+12μn + \frac{1}{2}\mu.

As in earlier efforts to prove ≥n+μ\ge n + \mu for several graph classes [15, 37], the high-level idea is to choose a maximum matching MM and a proper kk-colouring α\alpha, and then obtain a new colouring β\beta from α\alpha by interchanging the colours along each edge uvuv of MM, i.e. setting β(u)=α(v)\beta(u) = \alpha(v) and β(v)=α(u)\beta(v) = \alpha(u). Moreover, for every vertex uu not incident to MM, a colour β(u)\beta(u) distinct from α(u)\alpha(u) is chosen. If the resulting β\beta is also a proper kk-colouring then we are done: recolouring α\alpha to β\beta requires at least 3 recolouring steps on each edge of MM, so in total at least n+∣M∣n + |M| recolourings are needed to go from α\alpha to β\beta. The challenge with this approach is that there can be many bad choices of MM and α\alpha, for which β\beta is not proper. To avoid that difficulty, in the argument below, we instead interchange only a fraction of the vertices, in exchange for a weaker bound.

Theorem 14. Let GG be a graph with nn vertices, maximum degree Δ≥1\Delta\ge1, and matching number μ\mu. For every integer k≥Δ+2k \ge\Delta+ 2,

diam⁡Rk(G)≥n+min⁡(1,⌊k/2⌋Δ)μ.\operatorname{diam}\mathcal{R}_k(G) \ge n + \min\left(1,\frac{\lfloor k/2 \rfloor}{\Delta}\right)\mu.

Proof. Fix a maximum matching MM and let U=V(M)U = V(M) be the set of vertices that are an endpoint of some edge of MM. Let π:U→U\pi: U \to U be the function that interchanges the endpoints of every edge of MM. That is, π(u)=v\pi(u) = v and π(v)=u\pi(v) = u for every edge uvuv of MM. Define the supergraph G^\widehat{G} of G[U]G[U] with vertex set UU, and edges E(G^)=E(G[U])∪{π(x)π(y):xy∈E(G[U])}E(\widehat{G}) = E(G[U]) \cup\{\pi(x)\pi(y) : xy \in E(G[U])\}. Note that xy∈E(G^)xy \in E(\widehat{G}) if and only if π(x)π(y)∈E(G^)\pi(x)\pi(y) \in E(\widehat{G}). Moreover, G^\widehat{G} has maximum degree at most 2Δ−12\Delta- 1.

Take a palette of 2Δ2\Delta colours equipped with a fixed-point-free involution σ\sigma. That is, σ:[2Δ]→[2Δ]\sigma: [2\Delta] \to[2\Delta] is a function such that σ(c)≠c\sigma(c) \ne c and σ(σ(c))=c\sigma(\sigma(c)) = c for every c∈[2Δ]c \in[2\Delta]. We construct a proper colouring γ\gamma of G^\widehat{G} such that

γ(π(u))=σ(γ(u))for every u∈U.(2)\gamma(\pi(u)) = \sigma(\gamma(u)) \qquad\text{for every } u \in U. \tag*{(2)}

Process the edges of MM in arbitrary order. When an edge uvuv of MM is reached, each endpoint has at most 2Δ−22\Delta- 2 previously coloured neighbours. Let Cu,CvC_u, C_v be the colours on those previously coloured neighbours. Because the previously coloured vertices are the endpoints of some submatching of MM, the symmetry of G^\widehat{G} and the maintained property (2) on γ\gamma give Cv=σ(Cu)C_v = \sigma(C_u). Since ∣Cu∣≤2Δ−2|C_u| \le2\Delta- 2, we can choose a colour c∉Cuc \notin C_u. Then σ(c)∉σ(Cu)\sigma(c) \notin\sigma(C_u) because σ\sigma is an involution, and c≠σ(c)c \ne\sigma(c) because σ\sigma has no fixed point. Therefore we properly may extend the colouring to {u,v}\{u,v\} by setting γ(u)=c\gamma(u)=c and γ(v)=σ(c)\gamma(v)=\sigma(c). This completes the construction of γ\gamma.

For each c∈[2Δ]c \in[2\Delta], consider the set Mc:={uπ(u)∈M∣γ(u)∈{c,σ(c)}}M_c := \{u\pi(u) \in M \mid\gamma(u) \in\{c,\sigma(c)\}\} of edges in MM whose endpoints are coloured cc and σ(c)\sigma(c). Since Mc=Mσ(c)M_c=M_{\sigma(c)} for all cc, this partitions MM into Δ\Delta disjoint matchings. Put r=min⁡(Δ,⌊k/2⌋)r=\min(\Delta,\lfloor k/2\rfloor), and let M∗⊆MM^* \subseteq M be the union of the rr largest such matchings. Then

∣M∗∣≥⌈rΔ∣M∣⌉|M^*| \ge\left\lceil\frac{r}{\Delta}|M| \right\rceil

Based on M∗M^* and the colouring γ\gamma, we will now define two proper kk-colourings. Let U∗⊆UU^* \subseteq U be the endpoints of M∗M^*. The restriction of γ\gamma to U∗U^* uses at most 2r≤k2r \le k colours. Rename these colours into [k][k], and let α\alpha denote the resulting proper kk-colouring of G^[U∗]\widehat{G}[U^*]. As G^\widehat{G} is a supergraph of G[U]G[U], α\alpha is a proper kk-colouring of G[U∗]G[U^*] as well. On U∗U^*, define β(v)=α(π(v))\beta(v)=\alpha(\pi(v)). Then β\beta is a proper kk-colouring of G[U∗]G[U^*], since xy∈E(G[U∗])xy \in E(G[U^*]) implies π(x)π(y)∈E(G^[U∗])\pi(x)\pi(y) \in E(\widehat{G}[U^*]). By construction, α\alpha and β\beta differ at every vertex of U∗U^*, and interchange colours across each edge of M∗M^*.

Extend both colourings to GG, one new vertex at a time. At a new vertex vv, choose α(v)\alpha(v) to avoid its previously assigned neighbours in α\alpha. Then choose β(v)\beta(v) to avoid its previously assigned neighbours in β\beta and also to avoid α(v)\alpha(v). At most Δ+1\Delta+1 colours are forbidden in the latter step and k≥Δ+2k \ge\Delta+2, so both choices are possible. The resulting proper kk-colourings differ at every vertex of GG.

Every sequence from α\alpha to β\beta must change every vertex at least once. On an edge of M∗M^*, the first endpoint to change cannot immediately take its target colour, since that colour is still present at the other endpoint. Hence at least one endpoint of each edge of M∗M^* needs to be recoloured at least twice, so in total at least n+∣M∗∣n+|M^*| recolouring steps are needed. The bound on ∣M∗∣|M^*| proves the result.

Extension to hypergraphs

We end with a rather different topic, namely an extension to hypergraphs. These results were proved in 2024. The original plan was to write a separate paper about it. To prevent eternal procrastination, we present it here. Given a hypergraph H=(V,E)\mathcal{H}=(V,E), and a vertex v∈Vv \in V, let deg⁡∗(v)\deg^*(v) denote the maximum integer tt such that there are tt hyperedges e1,e2,…,et∈Ee_1,e_2,\ldots,e_t \in E such that v∈eiv \in e_i for all ii, and ei∩ej={v}e_i \cap e_j=\{v\} for all 1≤i<j≤t1 \le i<j \le t. In other words, deg⁡∗(v)\deg^*(v) is the maximum number of hyperedges containing vv that are pairwise vertex-disjoint outside vv. We can think of deg⁡∗(v)\deg^*(v) as the effective degree of vv. Let Δ∗:=max⁡v∈Vdeg⁡∗(v)\Delta^*:=\max_{v\in V}\deg^*(v) denote the maximum effective degree. A (proper) kk-colouring of H\mathcal{H} is a mapping c:V→{1,2,…,k}c:V\to\{1,2,\ldots,k\} such that no hyperedge e∈Ee\in E is monochromatic. The chromatic number χ(H)\chi(\mathcal{H}) of H\mathcal{H} is the smallest integer kk admitting a proper kk-colouring. Given an integer k≥0k \ge0, the kk-reconfiguration graph Rk(H)\mathcal{R}_k(\mathcal{H}) of H\mathcal{H} is the graph whose vertices are the proper kk-colourings of H\mathcal{H}, any two of which are adjacent if and only if they differ on precisely one vertex. Note that Rk(H)\mathcal{R}_k(\mathcal{H}) is non-empty if and only if k≥χ(H)k \ge\chi(\mathcal{H}). Throughout this section we assume that the hypergraph is loopless: every hyperedge of H\mathcal{H} contains at least two vertices, so that ∞≠χ(H)≤Δ∗(H)+1\infty\ne\chi(\mathcal{H}) \le\Delta^*(\mathcal{H})+1. We show that for such hypergraphs, the diameter of Rk(H)\mathcal{R}_k(\mathcal{H}) is also linear in nn.

Lemma 15. Let H\mathcal{H} be a loopless hypergraph on nn vertices and let k≥Δ∗(H)+2k \ge\Delta^*(\mathcal{H})+2. Then

n≤diam⁡Rk(H)≤2n−1n \le\operatorname{diam}\mathcal{R}_k(\mathcal{H}) \le2n-1

Proof. We first observe that at most deg⁡∗(v)\deg^{*}(v) colours are forbidden at any vertex vv. Indeed, suppose there are tt distinct colours d1,d2,…,dtd_1,d_2,\ldots,d_t such that assigning colour did_i to vv renders some hyperedge FiF_i monochromatic in did_i, for every i∈{1,2,…,t}i \in\{1,2,\ldots,t\}. Then Fi∩Fj={v}F_i \cap F_j = \{v\} whenever i≠ji \ne j, since any vertex in their intersection other than vv would have to receive both colours did_i and djd_j. Thus t≤deg⁡∗(v)t \le\deg^{*}(v).

The lower bound is immediate: take any kk-colouring α\alpha and permute the set of colours to obtain another kk-colouring β\beta such that α(v)≠β(v)\alpha(v) \ne\beta(v) for every vertex vv. Since each vertex needs to be recoloured at least once, at least nn recolourings are required.

For the upper bound, consider two proper kk-colourings α\alpha and β\beta. We describe a procedure that transforms α\alpha into β\beta, writing γ\gamma for the current colouring. Call a colour dd completed if β−1(d)⊆γ−1(d)\beta^{-1}(d) \subseteq\gamma^{-1}(d). Initially, γ=α\gamma= \alpha. Unless γ=β\gamma= \beta, there exists an uncompleted colour cc such that ∣γ−1(c)∣≤∣β−1(c)∣|\gamma^{-1}(c)| \leq|\beta^{-1}(c)|. Indeed, every completed colour dd satisfies ∣γ−1(d)∣≥∣β−1(d)∣|\gamma^{-1}(d)| \geq|\beta^{-1}(d)|. If every uncompleted colour satisfied the strict reverse of the desired inequality, summing over all colours would contradict ∑d∈[k]∣γ−1(d)∣=n=∑d∈[k]∣β−1(d)∣\sum_{d\in[k]}|\gamma^{-1}(d)| = n = \sum_{d\in[k]}|\beta^{-1}(d)|.

We now perform one phase of the procedure. First, iteratively recolour every vertex currently coloured cc to an available colour distinct from cc. By the initial observation and k≥deg⁡∗(v)+2k \geq\deg^{*}(v) + 2, such a colour always exists. Once there are no vertices with colour cc anymore, proceed with recolouring every vertex in β−1(c)\beta^{-1}(c) with cc. The latter recolourings are allowed in arbitrary order, since β−1(c)\beta^{-1}(c) contains no hyperedge. By the choice of cc, this phase requires at most ∣γ−1(c)∣+∣β−1(c)∣≤2∣β−1(c)∣|\gamma^{-1}(c)| + |\beta^{-1}(c)| \leq2|\beta^{-1}(c)| recolouring steps, and it makes cc completed.

Every previously completed colour dd remains completed. Indeed, the vertices of β−1(d)\beta^{-1}(d) have colour dd throughout the phase: they are neither vertices initially coloured cc nor vertices whose target colour is cc. Thus each phase increases the number of completed colours, and no completed colour is ever selected in a later phase. Repeating the procedure therefore eventually makes every colour completed, at which point γ=β\gamma= \beta. Since each colour is selected at most once and a phase selecting cc uses at most 2∣β−1(c)∣2|\beta^{-1}(c)| recolourings, the total number of recolourings is at most ∑c∈[k]2∣β−1(c)∣=2n\sum_{c\in[k]} 2|\beta^{-1}(c)| = 2n. If some colour dd with non-empty β−1(d)\beta^{-1}(d) is never selected, its contribution is omitted from the sum, saving at least two steps. Otherwise, in the final phase when the last colour dd is selected, every vertex outside β−1(d)\beta^{-1}(d) already has its target colour. Then we can recolour β−1(d)\beta^{-1}(d) directly to dd in at most ∣β−1(d)∣|\beta^{-1}(d)| steps, saving at least one step. □

Since hypergraphs can be used to represent a wide variety of combinatorial structures, it is clear that Lemma 15 has many corollaries. As an illustration, we mention two of them.

A vertex-colouring of a digraph is acyclic if there is no monochromatic directed cycle. We are interested in the reconfiguration graph whose vertices are the acyclic colourings, two of which adjacent iff they differ on precisely one vertex. Let Δmin⁡(G)=max⁡v∈V(G)min⁡(deg⁡−(v),deg⁡+(v))\Delta_{\min}(G) = \max_{v\in V(G)} \min(\deg^{-}(v),\deg^{+}(v)). For oriented graphs, Picasarri-Arrieta [35 Corollary 11] proved that the reconfiguration graph of acyclic kk-colourings has diameter at most 2Δmin⁡⋅n2\Delta_{\min} \cdot n, provided k≥Δmin⁡+1k \geq\Delta_{\min} + 1 and Δmin⁡≥1\Delta_{\min} \geq1. For arbitrary digraphs that bound is false. But with one additional allowed colour, the following gives a stronger bound for arbitrary digraphs.

Corollary 16. Let GG be a digraph with nn vertices and let kk be at least Δmin⁡(G)+2\Delta_{\min}(G) + 2. Then the diameter of the reconfiguration graph of acyclic kk-colourings of GG lies between nn and 2n−12n - 1.

Proof. Choose H\mathcal{H} the hypergraph with vertex set V(G)V(G), and with S⊆V(H)S \subseteq V(\mathcal{H}) a hyperedge if and only if SS is the vertex set of a directed cycle in GG. Every collection of tt directed cycles that contain a vertex vv but are disjoint outside vv implies the existence of tt disjoint pairs (e+,e−)(e^{+},e^{-}), where e+e^{+} (respectively e−e^{-}) is an ingoing (respectively outgoing) edge incident to vv. Therefore we have deg⁡∗(v)≤min⁡(deg⁡−(v),deg⁡+(v))\deg^{*}(v) \leq\min(\deg^{-}(v),\deg^{+}(v)), for every vertex vv. □

The vertex arboricity a(G)a(G) of a graph GG is the minimum number of colours in a vertex-colouring such that every monochromatic induced subgraph is a forest. Chartrand, Kronk and Wall [19] showed that a(G)≤⌊Δ(G)2⌋+1a(G) \le\left\lfloor\frac{\Delta(G)}{2} \right\rfloor+ 1. This also follows from Lovász’s decomposition theorem [33]. By taking one colour more, we get the reconfiguration analogue.

Corollary 17. Let GG be an nn-vertex graph and let k≥⌊Δ(G)2⌋+2k \ge\left\lfloor\frac{\Delta(G)}{2} \right\rfloor+ 2. Then the reconfiguration graph of kk-colourings of GG such that every monochromatic induced subgraph is a forest has diameter between nn and 2n−12n-1.

Proof. Choose the hypergraph on V(G)V(G) whose hyperedges are the vertex sets of cycles in GG. Since for every vertex vv, there are at most ⌊deg⁡(v)/2⌋\lfloor\deg(v)/2 \rfloor cycles containing vv while being pairwise disjoint outside vv, it follows that deg⁡∗(v)≤⌊deg⁡(v)/2⌋≤⌊Δ(G)/2⌋\deg^*(v) \le\lfloor\deg(v)/2 \rfloor\le\lfloor\Delta(G)/2 \rfloor.

Let k(H)k(\mathcal{H}) be the least integer such that diam⁡Rk(H)\operatorname{diam} \mathcal{R}_k(\mathcal{H}) has the same (finite) value for every k≥k(H)k \ge k(\mathcal{H}). We call this eventual value the stable diameter of H\mathcal{H}, and k(H)k(\mathcal{H}) the stability threshold. It is not hard to see that the stability threshold is finite. For graphs we know the stable diameter is n+μn+\mu, by Proposition 2.(i). This suggests a wider research program:

Question 18. Given a hypergraph, what are its stable diameter and stability threshold?

Open problems

While we have disproved all three variants in Conjecture 1, it raises more questions than answers. How does the diameter of the reconfiguration graph behave near the connectivity threshold Δ+2\Delta+2? Is there an elegant function that describes it for all graphs, or is the reality much more jagged and littered with exceptions? Which other graph invariants could play a role? Below, we propose some explicit problems for further research, some of which have been posed before.

  • Echoing the final question from [15]: what is the smallest ϵ>0\epsilon> 0 such that diam⁡RΔ(G)+2(G)≤n(G)+ϵ⋅μ(G)\operatorname{diam} \mathcal{R}_{\Delta(G)+2}(G) \le n(G) + \epsilon\cdot\mu(G) for every graph GG? By Theorem 3 and Proposition 2, we know that 3/2≤ϵ≤23/2 \le\epsilon\le2.

  • Conversely, what is the largest η>0\eta> 0 such that diam⁡RΔ(G)+2(G)≥n(G)+η⋅μ(G)\operatorname{diam} \mathcal{R}_{\Delta(G)+2}(G) \ge n(G) + \eta\cdot\mu(G) for every graph GG? By Theorem 7 and Proposition 2, we know that 1/2≤η≤11/2 \le\eta\le1. In [15] it was asked whether η=1\eta= 1.

  • What is the smallest integer Δ\Delta such that diam⁡RΔ+2(G)\operatorname{diam} \mathcal{R}_{\Delta+2}(G) is strictly larger than n(G)+μ(G)n(G) + \mu(G) for some graph GG with maximum degree Δ\Delta? The same can be asked with a restriction to Δ\Delta-regular graphs. In both cases we currently know via Theorems 3 and 4 that Δ∈{4,5,6,7,8}\Delta\in\{4,5,6,7,8\}.

  • Given a positive integer Δ\Delta, what is the smallest integer kΔk_\Delta such that diam⁡Rk(G)=n(G)+μ(G)\operatorname{diam} \mathcal{R}_k(G) = n(G) + \mu(G) for all k≥kΔk \ge k_\Delta and all graphs GG with maximum degree Δ\Delta? In other words, what is the stability threshold kΔk_\Delta such that the diameter settles on the stable diameter n(G)+μ(G)n(G) + \mu(G) for all k≥kΔk \ge k_\Delta? We presently know that kΔ=Δ+2k_\Delta= \Delta+ 2 for all Δ≤3\Delta\le3 due to De Meyer [26] but kΔ≥Δ+3k_\Delta\ge\Delta+ 3 for all even Δ>8\Delta> 8 due to Theorem 3. Moreover, kΔ≤2Δ+1k_\Delta\le2\Delta+ 1 for all Δ\Delta due to [15], which is sharp for Δ=1\Delta= 1. For Δ≥2\Delta\ge2, with some care the upper bound proof can be adapted to yield kΔ≤2Δk_\Delta\le2\Delta. In summary, Δ+3≤kΔ≤2Δ\Delta+ 3 \le k_\Delta\le2\Delta for infinitely many Δ\Delta.

  • Classify the graph classes for which the diameter of the kk-colouring reconfiguration graph is exactly equal to n+μn+\mu, for all k≥Δ+2k \ge\Delta+2. Is there a characterization in terms of forbidden induced subgraphs? If equality fails for a certain class, what is then the optimal bounding function in terms of nn and μ\mu? Other natural graph classes that come to mind are (outer)planar graphs.

  • Analogous questions can be asked for the list colouring and correspondence colouring variants described in [15]. In addition, Conjecture 4 in [15] is still open, concerning list colouring reconfiguration for graphs with bounded maximum average degree.

The main initial motivation for Conjecture 1 was a weaker one: is diam⁡RΔ(G)+2(G)≤32n(G)\operatorname{diam} \mathcal{R}_{\Delta(G)+2}(G) \le\frac{3}{2}n(G), for every graph GG? At the time we were inspired by an argument for complete graphs of Bonamy and Bousquet [3 Lemma 5] which was later developed further into the Optimal Renaming Lemma [17]. De Meyer [26] proved it is true for all complete multipartite and all subcubic graphs (compare Proposition 2), and it also holds for all bipartite graphs by Lemma 6. Is it true in general? If so, it is sharp for more than one reason: diameter ⌊3n/2⌋\lfloor3n/2\rfloor is attained by both KnK_n and Kn/2,n/2K_{n/2,n/2}. In terms of only the number of vertices, the current best upper bound (valid for every value of nn) is 2n−12n-1, from [15 Corollary 9]. Since the refinements in Conjecture 1 have now been disproved, we emphasize and explicitly state our (together with Cambie and Cranston) original motivating conjecture.

Conjecture 19. Let GG be a graph. If k≥Δ(G)+2k \ge\Delta(G)+2, then diam⁡Rk(G)≤32n(G)\operatorname{diam} \mathcal{R}_k(G) \le\frac{3}{2}n(G).

Declaration of AI use

Yes and no.

Declaration of AI use, expanded

The paper is a balanced recombination of human and AI-assisted (partial) proofs, both old and new, that went through dozens of iterations of alternating human and AI-assisted improvements, simplifications and rewriting. The result is a blurry symbiotic mix.

References

  1. [1][AKMZ25] Shamil Asgarlı, Sara Krehbiel, Simon MacLean, and Gjergji Zaimi (2025). Extremal diameters of 3-coloring graphs of trees. arXiv:2512.03789. ↑1arxiv.org/abs/2512.03789
  2. [2][BB13] Marthe Bonamy and Nicolas Bousquet (2013). Recoloring bounded treewidth graphs. Electronic Notes in Discrete Mathematics 44, 257–262. ↑1
  3. [3][BB18] Marthe Bonamy and Nicolas Bousquet (2018). Recoloring graphs via tree decompositions. European Journal of Combinatorics 69, 200–213. ↑1, 2, 13arxiv.org/abs/1403.6386
  4. [5][BBH21] Valentin Bartier, Nicolas Bousquet, and Marc Heinrich (2021). Recoloring graphs of treewidth 2. Discrete Mathematics 344(12), 112553. ↑1arxiv.org/abs/2012.11459
  5. [6][BBP21] Marthe Bonamy, Nicolas Bousquet, and Guillem Perrarnau (2021). Frozen (Δ + 1)-colourings of bounded degree graphs. Combinatorics, Probability and Computing 30(3), 330–343. ↑2DOI
  6. [7][BC25] Manoj Belavadi and Kathie Cameron (2025). Recoloring some hereditary graph classes. Discrete Applied Mathematics 361, 389–401. ↑2DOI
  7. [8][BCH25] Manoj Belavadi, Kathie Cameron, and Elias Hildred (2025). Frozen colourings in 2K₂-free graphs. Electronic Journal of Combinatorics 32(2), P2.29. ↑2
  8. [9]Manoj Belavadi, Kathie Cameron, and Owen Merkel (2024). Reconfiguration of vertex colouring and forbidden induced subgraphs. European Journal of Combinatorics 118, 103908. ↑2DOI
  9. [11]Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie (2025). Short and local transformations between (Δ + 1)-colorings. Innovations in Graph Theory 2, 119–156. ↑2
  10. [12]Nicolas Bousquet and Marc Heinrich (2022). A polynomial version of Cereceda’s conjecture. Journal of Combinatorial Theory, Series B 155, 1–16. ↑1arxiv.org/abs/1903.05619
  11. [13]Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, and Daniël Paulusma (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27(1), 132–143. ↑2
  12. [14]Nicolas Bousquet and Guillem Perarnau (2016). Fast recoloring of sparse graphs. European Journal of Combinatorics 52, 1–11. ↑1arxiv.org/abs/1411.6997
  13. [15]Stijn Cambie, Wouter Cames van Batenburg, and Daniel W. Cranston (2024). Optimally reconfiguring list and correspondence colourings. European Journal of Combinatorics 115, 103798. ↑2, 6, 7, 9, 12, 13DOI
  14. [16]Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Jan van den Heuvel, and Ross J. Kang (2025). Reconfiguration of list colourings. arXiv:2505.08020. ↑2arxiv.org/abs/2505.08020
  15. [17]Stijn Cambie, Wouter Cames van Batenburg, and Daniel W. Cranston (2026). Sharp bounds on lengths of linear recolouring sequences. Electronic Journal of Combinatorics 33(1), P1.18. ↑1, 13arxiv.org/abs/2412.19695
  16. [18]Luis Cereceda (2007). Mixing graph colourings. Ph.D. thesis, London School of Economics and Political Science. ↑2
  17. [19]Gary Chartrand, Hudson V. Kronk, and Curtiss E. Wall (1968). The point-arboricity of a graph. Israel Journal of Mathematics 6, 169–175. ↑12DOI
  18. [21]Daniel W. Cranston (2022). List-recoloring of sparse graphs. European Journal of Combinatorics 105, 103562. ↑1arxiv.org/abs/2201.05133
  19. [24]Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda (2006). Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structures & Algorithms 29(4), 450–465. ↑1DOI
  20. [26][DM26] Lucas De Meyer (2026). Optimal list recoloring of subcubic graphs and complete multipartite graphs. Discrete Mathematics 349(8), 115155. ↑2, 12, 13DOI
  21. [27][Feg21] Carl Feghali (2021). Reconfiguring colorings of graphs with bounded maximum average degree. Journal of Combinatorial Theory, Series B 147, 133–138. ↑1arxiv.org/abs/1904.12698
  22. [28][FJP16] Carl Feghali, Matthew Johnson, and Daniël Paulusma (2016). A reconfigurations analogue of Brooks’ theorem and its consequences. Journal of Graph Theory 83(4), 340–358. ↑2arxiv.org/abs/1501.05800
  23. [30][Heu13] Ian van den Heuvel (2013). The complexity of change. Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, vol. 409 (edited by Simon R. Blackburn, Stefanie Gerke, and Mark Wildon), 127–160. ↑1
  24. [31][Jer95] Mark Jerrum (1995). A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms 7(2), 157–165. ↑2DOI
  25. [33][Lov66] László Lovász (1966). On decomposition of graphs. Studia Scientiarum Mathematicarum Hungarica 1, 237–238. ↑12
  26. [34][Nis18] Naomi Nishimura (2018). Introduction to reconfiguration. Algorithms 11(4), 52. ↑1DOI
  27. [35][PA24] Lucas Picasarri-Arrieta (2024). Strengthening the directed Brooks’ theorem for oriented graphs and consequences on digraph recolouring. Journal of Graph Theory 106(1), 5–22. ↑11
  28. [36][WL26] Yichen Wang and Mei Lu (2026). Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs. Discrete Mathematics 349(7), 115055. ↑1arxiv.org/abs/2509.15456
  29. [37][Zev23] K. B. Zeven (2023). Reconfiguration of graph colorings. Bachelor’s thesis, Delft University of Technology. ↑2, 9

Paper details

vlnc:W_4buqvhmn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI-assisted

View statement
Looking for related papers…
Contents