Optimally Reconfiguring
List and Correspondence Colourings

Stijn Cambie Department of Mathematics, Radboud University Nijmegen, Netherlands and Mathematics Institute, University of Warwick, UK. E-mail: [email protected], supported by a Vidi grant (639.032.614) of the Netherlands Organisation for Scientific Research (NWO) and the UK Research and Innovation Future Leaders Fellowship MR/S016325/1. Current affiliation: Department of Computer Science, KU Leuven Campus Kulak-Kortrijk, 8500 Kortrijk, Belgium. Wouter Cames van Batenburg Delft University of Technology, Delft Institute of Applied Mathematics; [email protected] Daniel W. Cranston Virginia Commonwealth University, Department of Computer Science; [email protected]

Abstract

The reconfiguration graph $\mathcal{C}_{k}(G)$ for the $k$ -colourings of a graph $G$ has a vertex for each proper $k$ -colouring of $G$ , and two vertices of $\mathcal{C}_{k}(G)$ are adjacent precisely when those $k$ -colourings differ on a single vertex of $G$ . Much work has focused on bounding the maximum value of $\operatorname{diam}\mathcal{C}_{k}(G)$ over all $n$ -vertex graphs $G$ . We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if $L$ is a list-assignment for a graph $G$ with $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ , then $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+\mu(G)$ . We also conjecture that if $(L,H)$ is a correspondence cover for a graph $G$ with $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ , then $\operatorname{diam}\mathcal{C}_{(L,H)}(G)\leq n(G)+\tau(G)$ . (Here $\mu(G)$ and $\tau(G)$ denote the matching number and vertex cover number of $G$ .) For every graph $G$ , we give constructions showing that both conjectures are best possible, which also hints towards an exact form of Cereceda’s Conjecture for regular graphs. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+2\mu(G)$ and $\operatorname{diam}\mathcal{C}_{(L,H)}(G)\leq n(G)+2\tau(G)$ . Our second main result proves that both conjectured bounds hold, whenever all $v$ satisfy $|L(v)|\geq 2d(v)+1$ . We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree.

1 Introduction

In this paper we study questions of transforming one proper colouring of a graph $G$ into another, by a sequence of recolouring steps. Each step recolours a single vertex, and we require that each resulting intermediate colouring is also proper. Our work fits into the broader context of reconfiguration, in which some object (in our case a proper colouring) is transformed into another object of the same type, via a sequence of small changes, and we require that after each change we again have an object of the prescribed type (for us a proper colouring). It is natural to pose reconfiguration questions for a wide range of objects: proper colourings, independent sets, dominating sets, maximum matchings, spanning trees, and solutions to 3-SAT, to name a few. For each type of object, we must define allowable changes between successive objects in the sequence (in our case, recolouring a single vertex). Typically, we ask four types of questions. (1) Given objects $\alpha$ and $\beta$ , is there a reconfiguration sequence from $\alpha$ to $\beta$ ? (2) If the first question is answered yes, what is the length of a shortest such sequence? (3) Is the first question answered yes for every pair of objects $\alpha$ and $\beta$ ? (4) If yes, what is the maximum value of $\operatorname{dist}(\alpha,\beta)$ over all $\alpha$ and $\beta?$ For an introduction to reconfiguration, we recommend surveys by van den Heuvel [16] and Nishimura [15]. Most of our definitions and notation are standard, but for completeness we include many of them at the start of Section 2.

For a graph $G$ and a positive integer $k$ , the $k$ -colouring reconfiguration graph of $G$ , denoted $\mathcal{C}_{k}(G)$ , has as its vertices all proper $k$ -colourings of $G$ and two vertices of $\mathcal{C}_{k}(G)$ are adjacent if their corresponding colourings differ on exactly one vertex of $G$ . Our goal here is to study the diameter of this reconfiguration graph, denoted $\operatorname{diam}\mathcal{C}_{k}(G)$ . In general, $\mathcal{C}_{k}(G)$ may be disconnected, in which case its diameter is infinite. For example $\mathcal{C}_{2}(C_{2s})$ consists of two isolated vertices (here $C_{2s}$ is a cycle of length $2s$ ). More strongly, for each integer $k\geq 2$ there exist $k$ -regular graphs $G$ such that $\mathcal{C}_{k+1}(G)$ has isolated vertices. The simplest example is the clique $K_{k+1}$ , but this is also true for every $k$ -regular graph with a $(k+1)$ -colouring $\alpha$ such that all $k+1$ colours appear on each closed neighbourhood; such colourings are called frozen.

To avoid a colouring $\alpha$ being frozen, some vertex $v$ must have some colour unused by $\alpha$ on its closed neighbourhood, $N[v]$ . And to avoid $\mathcal{C}_{k}(G)$ being disconnected, every induced subgraph $H$ must contain such a vertex $v$ with some colour unused by $\alpha$ on $N[v]\cap V(H)$ . Thus, it is natural to consider the degeneracy of $G$ , denoted $\operatorname{degen}(G)$ .

Our examples of frozen colourings above show that, if we aim to have $\mathcal{C}_{k}(G)$ connected, then in general it is not enough to require $k\geq\operatorname{degen}(G)+1$ . However, an easy inductive argument shows that a slightly stronger condition is sufficient: If $k\geq\operatorname{degen}(G)+2$ , then $\mathcal{C}_{k}(G)$ is connected. (Earlier, Jerrum [12] proved that $k\geq\Delta(G)+2$ suffices, but the arguments are similar.) This inductive proof only yields that $\operatorname{diam}\mathcal{C}_{k}(G)\leq 2^{|V(G)|}$ . But Cereceda [7, Conjecture 5.21] conjectured something much stronger.

Cereceda’s Conjecture.

For an $n$ -vertex graph $G$ with $k\geq\operatorname{degen}(G)+2$ , the diameter of $\mathcal{C}_{k}(G)$ is $O(n^{2})$ .

Bousquet and Heinrich [6] proved that $\operatorname{diam}\mathcal{C}_{k}(G)=O_{d}(n^{\operatorname{degen}(G)+1})$ , which is the current best known bound. When $k\geq\Delta(G)+2$ , Cereceda [7, Proposition 5.23] proved that $\operatorname{diam}\mathcal{C}_{k}(G)=O(n\Delta)=O(n^{2})$ . In particular, Cereceda’s conjecture is true for regular graphs. But, as we show here, if $k\geq\Delta(G)+2$ , then in fact we have the stronger bound $\operatorname{diam}\mathcal{C}_{k}(G)\leq 2n$ , and we conjecture $\operatorname{diam}\mathcal{C}_{k}(G)\leq\lfloor 3n/2\rfloor$ .

A folklorish result observes that $\operatorname{diam}\mathcal{C}_{k}(G)=O(n)$ when $k$ is large relative to $\Delta(G)$ (for example, see [14, Section 3.1]). But until now, it seems that no one has investigated exact values of the diameter (say, when $k\geq\Delta(G)$ ). This is the main goal of our paper. Before stating our two main conjectures, and our results supporting them, we present an easy lower bound on $\mathcal{C}_{k}(G)$ in terms of the matching number $\mu(G)$ .

Proposition 1.

For a graph $G$ , if $k\geq 2\Delta(G)$ , then $\operatorname{diam}\mathcal{C}_{k}(G)\geq n(G)+\mu(G)$ .

Proof.

Let $M$ be a maximum matching in $G$ . Form $\widehat{G}$ from $G$ as follows. If $vw,xy\in M$ and $wx\in E(G)$ , then add $vy$ to $\widehat{G}$ . Note that $\Delta(\widehat{G})\leq 2\Delta(G)-1$ . So $\chi(\widehat{G})\leq 2\Delta(G)$ . Let $\alpha$ be a $2\Delta(G)$ -colouring of $\widehat{G}$ . Form $\beta$ from $\alpha$ by swapping colours on endpoints of each edge in $M$ and, for each $v\in V(G)$ not saturated by $M$ , picking $\beta(v)$ outside of $\{\alpha(v)\}\cup\bigcup_{w\in N(v)}\beta(w)$ . To recolour $G$ from $\alpha$ to $\beta$ , every vertex must be recoloured. Further, for each edge $e\in M$ , the first endpoint $v$ of $e$ to be recoloured must initially receive a colour other than $\beta(v)$ , so must be recoloured at least twice. Thus, $\operatorname{diam}\mathcal{C}_{k}(G)\geq n(G)+\mu(G)$ , as desired. ∎

At the end of Section 2, we mention various special cases in which the hypothesis of Proposition 1 can be weakened. We pose it as an open question whether the bound in Proposition 1 holds for all $k\geq\Delta(G)+2$ .

We study this reconfiguration problem in the more general contexts of list colouring and correspondence colouring, both of which we define in Section 2. These more general contexts offer the added advantage of enabling us to naturally prescribe fewer allowed colours for vertices of lower degree. Analogous to $\mathcal{C}_{k}(G)$ , for a graph $G$ and a list-assignment $L$ or correspondence cover $(L,H)$ for $G$ , we define the $L$ -reconfiguration graph $\mathcal{C}_{L}(G)$ or $(L,H)$ -reconfiguration graph $\mathcal{C}_{(L,H)}(G)$ of $G$ . Generalizing our constructions of frozen $k$ -colourings above, it is easy to show that $\mathcal{C}_{L}(G)$ and $\mathcal{C}_{(L,H)}(G)$ can contain frozen $L$ -colourings (and thus be disconnected) if we require only that all $v\in V(G)$ satisfy $\lvert L(v)\rvert=d(v)+1$ . Thus, we adopt a slightly stronger hypothesis: all $v\in V(G)$ satisfy $\lvert L(v)\rvert\geq d(v)+2$ . Now we can state our two main conjectures.

Conjecture 1 (List Colouring Reconfiguration Conjecture).

For a graph $G$ , if $L$ is a list-assignment such that $\lvert L(v)\rvert\geq d(v)+2$ for every $v\in V(G)$ , then $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+\mu(G)$ .

Conjecture 2 (Correspondence Colouring Reconfiguration Conjecture).

For a graph $G$ , if $(L,H)$ is a correspondence cover such that $\lvert L(v)\rvert\geq d(v)+2$ for every $v\in V(G)$ , then $\operatorname{diam}\mathcal{C}_{(L,H)}(G)\leq n(G)+\tau(G)$ .

Here $\tau(G)$ denotes the vertex cover number of $G$ . For brevity, we often call these conjectures the List Conjecture and the Correspondence Conjecture. Our aim in this paper is to provide significant evidence for both conjectures. Due to Proposition 1, the List Conjecture is best possible, when the lists are large enough. We will soon give easy constructions showing that both conjectures are best possible whenever all $v$ satisfy $|L(v)|\geq d(v)+2$ . But we defer these constructions until Section 2, where we formally define list and correspondence colourings.

Proposition 2.

For every graph $G$ (i) there exists a list-assignment $L$ such that $|L(v)|=d(v)+2$ for all $v$ for which $\operatorname{diam}\mathcal{C}_{L}(G)=n(G)+\mu(G)$ and (ii) there exists a correspondence cover $(L,H)$ such that $|L(v)|=d(v)+2$ for all $v$ for which $\operatorname{diam}\mathcal{C}_{(L,H)}(G)=n(G)+\tau(G)$ .

For both the List Conjecture and the Correspondence Conjecture, it is trivial to construct examples that need at least $n(G)$ recolourings. We simply require that $\alpha(v)\neq\beta(v)$ for all $n(G)$ vertices $v$ . So we view these conjectured upper bounds as consisting of a “trivial” portion, $n(G)$ recolourings, and a “non-trivial” portion, $\mu(G)$ or $\tau(G)$ recolourings. We give two partial results toward each conjecture. Our first result proves both conjectures up to a factor of 2 on the non-trivial portions of these upper bounds.

Theorem 1.

(i) For every graph $G$ and list-assignment $L$ with $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ we have $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+2\mu(G)$ . (ii) For every graph $G$ and correspondence cover $(L,H)$ with $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ we have $\operatorname{diam}\mathcal{C}_{(L,H)}(G)\leq n(G)+2\tau(G)$ .

Bousquet, Feuilloley, Heinrich, and Rabie [5, following Question 1.3] asked about the diameter of $\mathcal{C}_{k}(G)$ when $k=\Delta(G)+2$ . In this case, a result of Bonamy and Bousquet [3, Theorem 1] implies, for an $n$ -vertex graph $G$ and $k=\Delta(G)+2$ , that $\operatorname{diam}~{}\mathcal{C}_{k}(G)=O(\Delta(G)n)$ . The authors of [5] asked whether it is possible to remove this dependency on $\Delta(G)$ . We answer their question affirmatively. Always $\mu(G)\leq n(G)/2$ , so Theorem 1(i) implies that $\operatorname{diam}\mathcal{C}_{k}(G)\leq 2n(G)$ when $k=\Delta(G)+2$ .

To complement Theorem 1, we prove both conjectured upper bounds when $|L(v)|$ is sufficiently large.

Theorem 2.

(i) For every graph $G$ and list-assignment $L$ with $|L(v)|\geq 2d(v)+1$ for all $v\in V(G)$ we have $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+\mu(G)$ . (ii) For every graph $G$ and correspondence cover $(L,H)$ with $|L(v)|\geq 2d(v)+1$ for all $v\in V(G)$ we have $\operatorname{diam}\mathcal{C}_{(L,H)}(G)\leq n(G)+\tau(G)$ .

In Section 2 we present definitions and notation, as well as some easy lower bounds on diameters of reconfiguration graphs. In Section 3 we prove the list colouring portions of Theorems 1 and 2; and in Section 4 we prove the correspondence colouring portions. In Section 5 we prove more precise results when $G$ is a tree (in this case the correspondence problem is identical to the list problem).

In Sections 6 and 7, we conclude by proving one or both conjectures exactly for various graph classes, such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with low maximum average degree. These graphs are all sparse or have low chromatic number. On the other end of the sparsity spectrum, the List Conjecture is also true for all complete graphs, due to an argument of Bonamy and Bousquet [3, Lemma 5].

2 Definitions, Notation, and Easy Lower Bounds

For a graph $G=(V,E)$ , we denote its order by $n(G)$ . A matching is a set of vertex disjoint edges in $G$ . A matching $M$ of $G$ is perfect if it saturates every vertex of $G$ , and $M$ is near-perfect if it saturates every vertex of $G$ but one. A vertex cover $S$ is a vertex subset such that every edge of $G$ has at least one endpoint in $S$ . The matching number $\mu(G)$ of $G$ is the size of a largest matching. The vertex cover number $\tau(G)$ of $G$ is the size of a smallest vertex cover. (Recall that if $G$ is bipartite, then $\mu(G)=\tau(G)$ .)

The distance $\operatorname{dist}(v,w)$ between two vertices $v,w\in V(G)$ is the length of a shortest path in $G$ between $v$ and $w$ . The eccentricity of a vertex $v$ , denoted $\operatorname{ecc}(v)$ , is $\max_{w\in V}\operatorname{dist}(v,w).$ The diameter $\operatorname{diam}(G)$ of $G$ is $\max_{v,w\in V}\operatorname{dist}(v,w)$ , which is equal to $\max_{v\in V}\operatorname{ecc}(v)$ , while the radius $\operatorname{rad}(G)$ of $G$ is $\min_{v\in V}\operatorname{ecc}(v)$ . A diameter can also refer to a shortest path between $v$ and $w$ for which $\operatorname{dist}(v,w)=\operatorname{diam}(G).$ A graph $G$ is $k$ -degenerate if every non-empty subgraph $H$ contains a vertex $v$ such that $d_{H}(v)\leq k$ . The degeneracy of $G$ is the minimum $k$ such that $G$ is $k$ -degenerate.

A directed graph or digraph $D=(V,A)$ is analogous to a graph, except that each edge is directed. The directed edges in $A$ are ordered pairs of vertices, and are called arcs.

Definition 3.

For a digraph $D$ , the vertex cover number $\tau(D)$ and matching number $\mu(D)$ are defined to be $\tau(H_{D})$ and $\mu(H_{D})$ , where $H_{D}$ is the undirected graph with vertex set $V(D)$ whose edges correspond to the bidirected edges in $D$ .

Colourings are mappings from $V$ to ${\mathbb{N}}$ , and we denote them by greek letters such as $\alpha,\beta$ , and $\gamma$ . A colouring $\alpha$ of $G$ is proper if for every edge $vw\in E(G)$ we have $\alpha(v)\neq\alpha(w)$ . Let $[k]:=\{1,2,\ldots,k\}$ . A $k$ -colouring is a colouring using at most $k$ colours, which are generally from the set $[k]$ . The chromatic number $\chi(G)$ of $G$ is the smallest $k$ such that $G$ has a proper $k$ -colouring.

A list-assignment $L$ , for a graph $G$ , assigns to each $v\in V(G)$ a set $L(v)$ of natural numbers (“list” of allowable colours). A proper $L$ -colouring is a proper colouring $\alpha\colon V(G)\to{\mathbb{N}}$ such that $\alpha(v)\in L(v)$ for every $v\in V(G)$ . The list chromatic number (or choice number) $\chi_{\ell}(G)$ is the least $k$ such that $G$ admits a proper $L$ -colouring whenever every $v\in V(G)$ satisfies $\lvert L(v)\rvert\geq k$ .

A correspondence cover $(L,H)$ for a graph $G$ assigns to each vertex $v\in V(G)$ a set $L(v)$ of colours $\{(v,1),\ldots,$ $(v,f(v))\}$ and to each edge $vw\in E(G)$ a matching between $L(v)$ and $L(w)$ . (In this paper, we typically consider either $f(v)=d(v)+2$ or $f(v)=2d(v)+1$ for all $v\in V(G)$ .) Given a correspondence cover $(L,H)$ , an $(L,H)$ -colouring of $G$ is a function $\alpha$ such that $\alpha\in L(v)$ for all $v$ and whenever $vw\in E(G)$ the edge $\alpha(v)\alpha(w)$ is not an edge of the matching assigned to $vw$ . Here $H$ denotes the union of the matchings assigned to all edges of $G$ . (It is easy to check that correspondence colouring generalises list colouring.)

The reconfiguration graph $\mathcal{C}_{k}(G)$ has as its vertices the proper $k$ -colourings of $G$ , and two $k$ -colourings $\alpha$ and $\beta$ are adjacent in $\mathcal{C}_{k}(G)$ if they differ on exactly one vertex of $G$ . In particular, if $k<\chi(G)$ , then $\mathcal{C}_{k}(G)$ has no vertices. (The reconfiguration graph was first defined in [8], where it was called the $k$ -colour graph.) The distance between $k$ -colourings $\alpha$ and $\beta$ is at most $j$ if we can form $\beta$ , starting from $\alpha$ , by recolouring at most $j$ vertices, one at a time, so that after each recolouring the current $k$ -colouring of $G$ is proper. Similarly, for a graph $G$ and list-assignment $L$ , the reconfiguration graph $\mathcal{C}_{L}(G)$ , or reconfiguration graph of the $L$ -colourings of $G$ , is the graph whose vertices are the proper $L$ -colourings of $G$ . Again, two $L$ -colourings $\alpha$ and $\beta$ are adjacent in $\mathcal{C}_{L}(G)$ if they differ on exactly one vertex. This extension was first defined in [4]. For a correspondence cover $(L,H)$ , the reconfiguration graph $\mathcal{C}_{(L,H)}(G)$ is defined analogously; its vertices are the correspondence colourings of $G$ and two vertices of $\mathcal{C}_{(L,H)}(G)$ are adjacent precisely when their colourings differ on exactly one vertex of $G$ . We will also use the associated colour-shift digraph for a graph $G$ and two proper colourings, which is defined as follows.

Definition 4.

Let $G=(V,E)$ be a graph and $\alpha$ and $\beta$ be two proper colourings of $G$ . We define an associated colour-shift digraph $D_{\alpha,\beta}=(V,A)$ where $\overrightarrow{vw}\in A$ if and only if $vw\in E$ and $\beta(v)=\alpha(w)$ .

2.1 Improved Lower Bounds

In this subsection we prove lower bounds which show that our upper bounds in the rest of the paper are sharp or nearly sharp. These will not be explicitly needed elsewhere, so the impatient reader should feel free to skip to Section 3, where we prove Theorems 1(i) and 2(i).

Observation 5.

If $G$ is a graph with list colourings $\alpha$ and $\beta$ , then $\operatorname{dist}(\alpha,\beta)\geq\mu(D_{\alpha,\beta})+\sum_{v\in V}\mathbf{1}_{\alpha(v)\not=\beta(v)}$ .

Proof.

Whenever $\alpha(v)\not=\beta(v)$ , vertex $v$ must be recoloured. Further, if $v$ and $w$ are neighbours for which $\alpha(v)=\beta(w)$ and $\alpha(w)=\beta(v)$ , then we cannot recolour both $v$ and $w$ only once, since after every recolouring step the resulting colouring must be proper. So at least $\sum_{v\in V}\mathbf{1}_{\alpha(v)\not=\beta(v)}$ vertices must be recoloured, and at least $\mu(D_{\alpha,\beta})$ vertices must be recoloured at least twice. ∎

Does the lower bound in Observation 5 always hold with equality? Our next example shows that it does not; see Figure 1. Specifically, this example exhibits, for the 4-cycle, colourings $\alpha$ and $\beta$ such that $\mu(D_{\alpha,\beta})<\mu(G)$ but still $\operatorname{dist}(\alpha,\beta)=n(G)+\mu(G)$ .

Example 6.

Let $G=C_{4}$ and denote $V(G)$ by $[4]$ . If $\alpha(i)=i$ and $\beta(i)\equiv i+1\pmod{4}$ and the colour set is precisely $[4]$ , then transforming $\alpha$ to $\beta$ uses at least 6 recolourings, i.e. $\operatorname{dist}(\alpha,\beta)=6$ . Part of this reconfiguration graph is shown in Figure 1.

Proof.

Starting from $\alpha$ , each vertex $i$ has a single colour with which it can be recoloured. But each possible recolouring creates a colouring $\alpha^{\prime}$ for which Observation 5 gives $\operatorname{dist}(\alpha^{\prime},\beta)\geq 5$ . ∎

Figure 1: Part of the reconfiguration graph

\mathcal{C}_{4}(C_{4})

Next we present the (previously promised) proof of Proposition 2. For easy reference, we restate it.

Proposition 2.

Proof.

For a graph $G$ , fix a maximum matching $M$ . Assign to each vertex $v$ a list of $d(v)+2$ colours such that $|L(v)\cap L(w)|=2$ if $vw\in M$ and otherwise $|L(v)\cap L(w)|=0$ . Pick $\alpha$ and $\beta$ such that for each $vw\in M$ , we have $\alpha(v)=\beta(w)$ and $\alpha(w)=\beta(v)$ , and for each $v\in V(G)$ we have $\alpha(v)\not=\beta(v).$ The lower bound holds by Observation 5. The upper bound is trivial, since $L(x)\cap L(y)=\emptyset$ for all $xy\in E(G)\setminus M$ . This proves (i).

Let $(L,H)$ be a correspondence cover of $G$ such that $L(v)=\{(v,1)\ldots(v,d(v)+2)\}$ for every $v\in V(G)$ . For every $vw\in E(G)$ , let the matching (from $H$ ) consist of the two edges $(v,1)(w,2)$ and $(v,2)(w,1)$ ; otherwise, $(v,i)$ and $(w,j)$ are unmatched. Let $\alpha(v):=(v,1)$ and $\beta(v):=(v,2)$ for all $v\in V(G)$ . Starting from $\alpha$ , we can recolour a vertex $v$ with $\beta(v)$ only if all neighbours of $v$ have already been recoloured. Thus, the set of vertices recoloured only once must be an independent set; equivalently, the set of vertices recoloured at least twice must be a vertex cover. So we must use at least $n(G)+\tau(G)$ recolourings, which proves the lower bound. For the upper bound, fix a minimum vertex cover $S$ . First recolour each $v\in S$ with $(v,3)$ ; afterward, recolour each vertex with $(v,2)$ , first the vertices in $V(G)\backslash S$ and then those in $S$ . So $n(G)+\tau(G)$ recolourings suffice. This proves (ii). ∎

It is helpful to note that the proof of Proposition 2 actually works (for both list colouring and correspondence colouring) whenever all $v$ satisfy $|L(v)|\geq 3$ .

Clearly, the graph $\widehat{G}$ constructed in Proposition 1 depends on our choice of a perfect matching $M$ . It is interesting to note that some choices of $M$ work quite well, while others work rather poorly.

Example 7.

Figure 2 shows a graph $G$ built from two cliques $K_{p}$ and a complete bipartite graph $K_{p,p}$ , with parts $U$ and $W$ , by adding a perfect matching $M$ between one copy of $K_{p}$ and the vertices of $U$ and a perfect matching between $W$ and the other copy of $K_{p}$ . Now $\chi(\widehat{G})=2p$ if we choose our perfect matching to be $M$ . If $p$ is even, then we can instead choose a perfect matching $M^{\prime}$ that is the disjoint union of perfect matchings in the two copies of $K_{p}$ and in the $K_{p,p}$ so that the resulting $\widehat{G}$ instead satisfies $\chi(\widehat{G})=p+2$ .

Figure 2: A graph

G

(shown on both left and right) consisting of a complete bipartite graph

K_{p,p}

in the center, two copies of

K_{p}

on the sides, and a matching from each copy of

K_{p}

to one part of

K_{p,p}

. The left and right figures specify different perfect matchings

M

(in bold). On the left,

\chi(\widehat{G})\geq\omega(\widehat{G})=|V(K_{p,p})|=2p=2\Delta(G)-2

. On the right,

\omega(\widehat{G})=\omega(G)=p

, and in fact

\chi(\widehat{G})\leq p+2=\Delta(G)+1

. (We use colours

1,\ldots,p

on each clique and colours

p+1

and

p+2

in the center.)

Although Example 7 implies that our choice of $M$ can effect $\chi(\widehat{G})$ dramatically, for many graphs, any choice of $M$ is fine. To conclude this section, we present various cases in which (for all choices of $M$ ) we can weaken the hypothesis of Proposition 1.

Proposition 3.

For a graph $G$ and positive integer $k$ we have

\operatorname{diam}~{}\mathcal{C}_{k}(G)\geq n(G)+\mu(G)

whenever (a) $\chi(\widehat{G})\leq k-1$ or (b) $\chi(\widehat{G})\leq k$ and $k\geq\Delta(G)+2$ , where $\widehat{G}$ is as in Proposition 1. In particular, this is true in the following cases.

$(1)$

$1+\chi(G)(\chi(G)-1)\leq k$ (in particular, if $G$ is bipartite and $k\geq 3$ ).
$(2)$

$\Delta(G)=3$ and $k\geq\Delta(G)+2=5$ .
$(3)$

$\chi(G)\leq 3$ and $k\geq\Delta(G)+2$ (in particular, if $G$ is outerplanar and $k\geq\Delta(G)+2$ ).
$(4)$

$k\geq\Delta(G)+3$ and $G$ is triangle-free, if Reed’s Conjecture¹¹1Recall that Reed conjectured that $\chi(G)\leq\left\lceil(\Delta(G)+1+\omega(G))/2\right\rceil$ for every graph $G$ . holds for every graph $\widehat{G}$ with $\omega(\widehat{G})\leq 5$ .
$(5)$

$k\geq\Delta(G)+2$ and $\Delta(G)>f(\omega(G))$ for some function $f$ .

Proof.

Recall the definition of $\widehat{G}$ from Proposition 1. Let $M$ be a maximum matching in $G$ . Form $\widehat{G}$ from $G$ as follows. If $vw,xy\in M$ and $wx\in E(G)$ , then add $vy$ to $\widehat{G}$ . To prove each case of the proposition, we construct the graph $\widehat{G}$ , let $\alpha$ be a $\chi(\widehat{G})$ -colouring of $\widehat{G}$ (which is also a $\chi(\widehat{G})$ -colouring of $G$ ), and form a $k$ -colouring $\beta$ from $\alpha$ by swapping the colours on the endpoints of each edge $e$ in the specified maximum matching $M$ ; for each $v$ not saturated by $M$ , we choose $\beta(v)$ to avoid $\alpha(v)\cup\bigcup_{x\in N(v)}\beta(x)$ . The latter is possible because we assumed that $k$ is bounded from below by $\chi(\widehat{G})+1$ or by $\Delta(G)+2$ . By Observation 5, we have $\operatorname{dist}(\alpha,\beta)\geq\mu(D_{\alpha,\beta})+\sum_{v\in V}\mathbf{1}_{\alpha(v)\not=\beta(v)}=\mu(G)+n(G)$ . Note that $\Delta(\widehat{G})\leq 2\Delta(G)-1$ . So $\chi(\widehat{G})\leq 1+\Delta(\widehat{G})\leq 2\Delta(G)$ . Now we show that in each case listed above we have $\chi(\widehat{G})\leq k$ or (in the first case) $\chi(\widehat{G})\leq k-1$ .

$(1)$

Fix a $\chi(G)$ -colouring $\alpha$ of $G$ . We assume that $M$ is a perfect matching; if not, then we add a pendent edge at each vertex that is unsaturated by $M$ and add all these new edges to $M$ . To colour $\widehat{G}$ , we give each vertex $v$ the colour $(i,j)$ , where $\alpha(v)=i$ , $\alpha(w)=j$ , and $vw\in M$ . It is easy to check that the resulting colouring of $\widehat{G}$ is proper.
$(2)$

Suppose that $\Delta(G)=3$ . As noted above, we have $\Delta(\widehat{G})\leq 2\Delta(G)-1=5$ . If $\Delta(\widehat{G})\leq 4$ , then $\chi(\widehat{G})\leq 5$ as desired. So assume instead that $\Delta(\widehat{G})=5$ . By Brooks’ Theorem it suffices to show that no component of $\widehat{G}$ is $K_{6}$ . Suppose, to the contrary, that there exists $S\subseteq V(G)$ such that $\widehat{G}[S]=K_{6}$ . It is easy to check that $G[S]$ must be 3-regular, and every vertex of $S$ must be saturated by $M$ . Observe that if two edges of $M$ , say $v_{1}v_{2},v_{3}v_{4}$ lie on a 4-cycle in $G$ , then $d_{\widehat{G}}(v_{i})\leq 4$ , for each $i\in\{1,2,3,4\}$ . Now we need only to check that such a configuration occurs for every 3-regular graph $G$ on 6 vertices and every perfect matching $M$ . This is straightforward to verify: $G-M$ is either a 6-cycle or two 3-cycles; in the first case, $M$ can be added in two (non-isomorphic) ways and in the second, $M$ can be added in only one way.
$(3)$

If $\Delta(G)\geq 4$ , then we are done by condition $(1)$ . If $\Delta(G)=3$ , then we are done by condition $(2)$ . If $\Delta(G)=2$ , then we are done by Proposition 1. And if $\Delta(G)\leq 1$ , then we are done trivially.
$(4)$

We show that if $G$ is triangle-free, then $\omega(\widehat{G})\leq 5$ . Suppose, to the contrary, that $\omega(\widehat{G})\geq 6$ . Consider $S\subseteq V(G)$ such that $\widehat{G}[S]=K_{6}$ , and colour each edge of $\widehat{G}[S]$ with 1 if it appears in $G$ and with 2 otherwise. Since $G$ is triangle-free, $\widehat{G}[S]$ has no triangle coloured 1. Let $R(t,t)$ denote the diagonal Ramsey number for cliques of order $t$ . Since $R(3,3)=6$ , we must have a triangle in $\widehat{G}[S]$ that is coloured 2; denote its vertices by $v,w,x$ . Let $vv^{\prime},ww^{\prime},xx^{\prime}$ denote the edges of $M$ incident with $v,w,x$ . Since $vw,vx,wx\in E(\widehat{G})\setminus E(G)$ , we conclude that $v^{\prime}w^{\prime},v^{\prime}x^{\prime},w^{\prime}x^{\prime}\in E(G)$ . This contradicts that $G$ is triangle-free. Hence, $\omega(\widehat{G})\leq 5$ , as claimed. Finally, by Reed’s Conjecture, $\chi(\widehat{G})\leq\left\lceil(\Delta(\widehat{G})+\omega(\widehat{G})+1)/2\right\rceil\leq\left\lceil(2\Delta(G)-1+5+1)/2\right\rceil\leq\Delta(G)+3\leq k$ .
$(5)$

Let $t$ be a positive integer and consider any graph $G$ with $\omega(G)=t$ . Note that $\widehat{G}$ can be decomposed into two (edge-disjoint) copies of $G$ ; here $\widehat{G}$ is formed from the two copies of $G$ by identifying, for each edge $vw\in M$ , the instance of $v$ in one copy of $G$ with the instance of $w$ in the other copy. This implies that $\omega(\widehat{G})<R(t+1,t+1)$ . We also know that $\Delta(\widehat{G})\leq 2\Delta(G).$ Now by e.g. [13, Theorem 2] we have

$\chi(\widehat{G})\leq 200R(t+1,t+1)\frac{2\Delta(G)\ln\ln(2\Delta(G))}{\ln(2\Delta(G))}.$

This is smaller than $\Delta(G)+2$ whenever $\Delta(G)$ is sufficiently large.

∎

We also consider the graph $\tilde{G}$ formed from $G$ by contracting each edge of a maximum matching $M$ .

Proposition 4.

For a graph $G$ and positive integer $k$ we have

\operatorname{diam}~{}\mathcal{C}_{k}(G)\geq n(G)+\mu(G)

whenever $k\geq 2\chi(\tilde{G})$ for some maximum matching of $G$ . In particular, this is

$(1)$

true a.a.s. for $G_{n,p}$ , for fixed $p\in(0,1)$ , and $k\geq\Delta(G_{n,p})+2.$
$(2)$

true if $G$ is $K_{t+1}$ -minor free and $k\geq 2t$ , provided Hadwiger’s Conjecture²²2Recall that Hadwiger conjectured that $\chi(G)\leq t$ for every graph $G$ with no $K_{t+1}$ -minor. holds for $K_{t+1}$ -minor free graphs. The latter is true for $t\leq 5$ .

Proof.

Let $\tilde{\alpha}$ be a $\chi(\tilde{G})$ -colouring of $\tilde{G}$ . We construct a $2\chi(\tilde{G})$ -colouring $\alpha$ of $G$ such that if $v\in V(\tilde{G})$ and $v$ arises from contracting edge $wx\in M$ and $\tilde{\alpha}(v)=i$ , then $\{\alpha(w),\alpha(x)\}=\{2i-1,2i\}$ ; if $v$ does not arise from contracting an edge, then we choose $\alpha(v)=2\tilde{\alpha}(v)=2i$ . Form $\beta$ from $\alpha$ by swapping the colours on the endpoints of each edge of $M$ and letting $\beta(v):=\alpha(v)-1=2i-1$ for each $v\in V(G)\backslash M$ .

Hence $\operatorname{diam}\mathcal{C}_{k}(G)\geq\operatorname{dist}(\alpha,\beta)\geq n(G)+\mu(G)$ by Observation 5. We now prove that in the two mentioned cases, we (a.a.s.) have $k\geq 2\chi(\tilde{G})$ , regardless of the maximum matching of $G$ we choose to form $\tilde{G}$ .

$(1)$

Let $G:=G_{n,p}$ . By [2], the Hadwiger number $h$ (or contraction clique number) of $G$ for fixed $p\in(0,1)$ is $\Theta\left(\frac{n}{\sqrt{\ln n}}\right)$ a.a.s., so $G$ is $K_{h+1}$ -minor free. Note that $\tilde{G}$ is also $K_{h+1}$ -minor free. By recent progress towards Hadwiger’s conjecture, culminating in [9], this implies that (still a.a.s.) $\chi(\tilde{G})=O(h\ln\ln h)=O\left(\frac{n\ln\ln n}{\sqrt{\ln n}}\right)$ . So $\chi(\tilde{G})$ is a.a.s. smaller than $\Delta(G_{n,p})+2$ , which is $np(1+o(1))=\Theta(n).$
$(2)$

Note that $\tilde{G}$ is also $K_{t+1}$ -minor free. So, by assumption, $\chi(\tilde{G})\leq t$ .

∎

Question 1.

Is it true, for every graph $G$ and every $k\geq\Delta(G)+2$ , that $\operatorname{diam}~{}\mathcal{C}_{k}(G)\geq n(G)+\mu(G)$ ?

If the answer to this question is yes, then the List Conjecture (if true) would imply that $\operatorname{diam}~{}\mathcal{C}_{k}(G)=n(G)+\mu(G)$ for every graph $G$ and every $k\geq\Delta(G)+2$ . In particular, this would constitute a precise version for Cereceda’s Conjecture in the case of regular graphs.

3 Proving the Main Results for Lists

In this section, we prove the list colouring portions of our main results: Theorems 1(i) and 2(i). Recall that a graph $G$ is factor-critical if $|V(G)|$ is odd and $G-v$ has a perfect matching for each $v\in V(G)$ . Gallai showed that if every vertex is unsaturated by some maximum matching, i.e., $\mu(G-v)=\mu(G)$ for every vertex $v$ , then $G$ is factor-critical. So, in each proof we begin with a lemma to handle factor-critical graphs, and thereafter proceed to the general case. The following lemma serves as the base case in an inductive proof of Theorem 1(i). (We will only need it when $G$ is factor-critical, but we prove it for all $G$ .)

Lemma 8.

Let $G$ be graph and let $L$ be a list-assignment for $G$ such that $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ . If $\alpha$ and $\beta$ are $L$ -colourings of $G$ , then we can recolour $G$ from $\alpha$ to $\beta$ in at most $2n(G)-1$ steps.

Proof.

We use induction on $|\beta(V(G))|$ . The case $|\beta(V(G))|=1$ , is trivial, since then $G$ is an independent set; starting from $\alpha$ , we can recolour each vertex $v$ to $\beta(v)$ . We use at most $n(G)$ recolouring steps, which suffices since $n(G)\leq 2n(G)-1$ .

Now assume $|\beta(V(G))|\geq 2$ . For each colour $c$ , let $\alpha^{-1}(c):=\{v\in V(G)\mbox{ s.t. }\alpha(v)=c\}$ and $\beta^{-1}(c):=\{v\in V(G)\mbox{ s.t. }\beta(v)=c\}$ . Since $\sum_{c\in\alpha(V(G))}|\alpha^{-1}(c)|=n(G)=\sum_{c\in\beta(V(G))}|\beta^{-1}(c)|$ , there exists $c$ such that $|\alpha^{-1}(c)|\leq|\beta^{-1}(c)|$ . Starting from $\alpha$ , for each $v\in\alpha^{-1}(c)$ , recolour $v$ to avoid colour $c$ . Now for each $v\in\beta^{-1}(c)$ , recolour $v$ with $c$ . After at most $2|\beta^{-1}(c)|$ steps, we have $|\beta^{-1}(c)|$ more vertices that are coloured to agree with $\beta$ . Now we delete these $|\beta^{-1}(c)|$ vertices, and delete the colour $c$ from $L(v)$ whenever $v$ had some neighbours in $\beta^{-1}(c)$ , and finish by induction. ∎

Corollary 9.

For every graph $G$ and every $k\geq\Delta(G)+2$ , the diameter of $\mathcal{C}_{k}(G)$ is at most $2n(G)-1$ .

Now we prove Theorem 1(i). For easy reference, we restate it below.

Theorem 10.

Let $G$ be an $n$ -vertex graph and $L$ be a list-assignment with $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ . If $\alpha$ and $\beta$ are $L$ -colourings of $G$ , then we can recolour $G$ from $\alpha$ to $\beta$ in at most $n(G)+2\mu(G)$ steps.

Proof.

We use induction on $n(G)$ . We assume $G$ is connected; otherwise, we handle each component separately. (This suffices because, for a graph $G$ with components $G_{1},\ldots,G_{s}$ , we have $n(G)=\sum_{i=1}^{s}n(G_{i})$ and $\mu(G)=\sum_{i=1}^{s}\mu(G_{i})$ .) If $\mu(G-v)=\mu(G)$ for all $v\in V(G)$ , then $G$ is factor-critical. This is an easy result of Gallai, but also follows from Theorem 12(2). Now $n(G)+2\mu(G)=2n(G)-1$ , so we are done by Lemma 8.

Assume instead that some vertex $v$ is saturated by every maximum matching. Note that $2d(v)<2|L(v)|$ . By Pigeonhole there exists $c\in L(v)$ such that $|\beta^{-1}(c)\cap N(v)|+|\alpha^{-1}(c)\cap N(v)|\leq 1$ . (We handle the case when equality holds, since the other case is easier.) Assume there exists $w\in N(v)$ such that $\alpha(w)=c$ and $c\notin\cup_{x\in N(v)\setminus\{w\}}\{\alpha(x),\beta(x)\}$ . (If instead $\beta(w)=c$ , then we swap the roles of $\alpha$ and $\beta$ .) Form $\tilde{\alpha}$ from $\alpha$ by recolouring $w$ from $L(w)\setminus(\alpha(N(w))\cup\{c\})$ and recolouring $v$ with $c$ . Let $G^{\prime}:=G-v$ . Let $L^{\prime}(x):=L(x)-c$ for all $x\in N(v)$ and $L^{\prime}(x):=L(x)$ for all other $x\in V(G^{\prime})$ . Denote the restrictions to $G^{\prime}$ of $\tilde{\alpha}$ and $\beta$ by $\tilde{\alpha}^{\prime}$ and $\beta^{\prime}$ . By induction, we can recolour $G^{\prime}$ from $\tilde{\alpha}^{\prime}$ to $\beta^{\prime}$ in at most $n(G^{\prime})+2\mu(G^{\prime})$ steps. After this, we can finish by recolouring $v$ with $\beta(v)$ . Thus, $\operatorname{dist}_{L}(\alpha,\beta)\leq 2+\operatorname{dist}_{L^{\prime}}(\tilde{\alpha}^{\prime},\beta^{\prime})+1\leq 2+n(G^{\prime})+2\mu(G^{\prime})+1=2+n(G)-1+2(\mu(G)-1)+1=n(G)+2\mu(G)$ . ∎

To prove Theorem 2(i), we will use the following lemma to handle the case when $G$ is factor-critical.

Lemma 11.

Let $G$ be a graph and let $L$ be a list-assignment for $G$ such that $|L(v)|\geq 2d(v)+1$ for all $v\in V(G)$ . If $\alpha$ and $\beta$ are $L$ -colourings of $G$ , then we can recolour $G$ from $\alpha$ to $\beta$ in at most $\left\lfloor\frac{3n(G)}{2}\right\rfloor$ steps.

Proof.

Let $\alpha$ and $\beta$ be arbitrary $L$ -colourings of $G$ . (Recall that all colours are positive integers.) Let $V_{1}$ and $V_{2}$ be the subsets of $V(G)$ , respectively, for which $\alpha(v)>\beta(v)$ and $\alpha(v)<\beta(v)$ . Let $n_{1}:=|V_{1}|$ and $n_{2}:=|V_{2}|$ . Since $n_{1}+n_{2}\leq n(G)$ , we assume by symmetry that $n_{1}\leq\frac{n(G)}{2}$ ; otherwise, we interchange $\alpha$ and $\beta$ . We show how to recolour $G$ from $\alpha$ to $\beta$ using at most $n(G)+n_{1}\leq n(G)+\left\lfloor\frac{n(G)}{2}\right\rfloor$ steps.

First, iteratively for every $v\in V_{1}$ we recolour $v$ from $L(v)\setminus\cup_{w\in N(v)}\{\beta(w),\gamma(w)\}$ , where $\gamma$ is the current colouring of $G$ . By definition this recolouring is proper (we actually do not need to recolour $v$ if $\gamma(v)\not=\beta(w)$ for all $w\in N(v)$ ). Next, iteratively for $j$ from $\max\{\cup_{v\in V}L(v)\}$ to $\min\{\cup_{v\in V}L(v)\}$ , we recolour with $j$ all vertices $v\in V(G)$ for which $\beta(v)=j$ . In these steps, we only have proper colourings, as we will now show. Consider a neighbour $w$ of $v$ . If $w$ has already been recoloured with some $\gamma(w)$ , then $\gamma(w)\neq\beta(v)$ , by construction. If $w$ has not been recoloured, then $\alpha(w)\leq\beta(w)<\beta(v)$ . ∎

The following classical result is helpful in our proof of Theorem 2(i).

Theorem 12 (Edmonds–Gallai Decomposition Theorem).

For a graph $G$ , let

$V_{1}(G):=\{v\in V(G)$ such that some maximum matching avoids $v\}$ ,
$V_{2}(G):=\{v\in V(G)$ such that $v$ has a neighbour in $V_{1}(G)$ , but $v\notin V_{1}(G)\}$ ,
$V_{3}(G):=V(G)\setminus(V_{1}(G)\cup V_{2}(G))$ .

Now the following statements hold.³³3We prefer the names $V_{1}(G)$ , $V_{2}(G)$ , $V_{3}(G)$ over the standard terminology $D(G)$ , $A(G)$ , and $C(G)$ , since the latter terms conflict with our use of $D=(V,A)$ for a digraph $D$ with vertex set $V$ and arc set $A$ .

$(1)$

The subgraph induced by $V_{3}(G)$ has a perfect matching.
$(2)$

The components of the subgraph induced by $V_{1}(G)$ are factor-critical.
$(3)$

If $M$ is any maximum matching, then $M$ contains a perfect matching of each component of $V_{3}(G)$ , and $M$ contains a near-perfect matching of each component of $V_{1}(G)$ , and $M$ matches all vertices of $V_{2}(G)$ with vertices in distinct components of $V_{1}(G)$ .
$(4)$

$\mu(G)=\frac{1}{2}\left(|V(G)|-c(V_{1}(G))+|V_{2}(G)|\right)$ , where $c(V_{1}(G))$ denotes the number of components of the graph spanned by $V_{1}(G)$ .

Now we prove Theorem 2(i). For easy reference, we restate it below.

Theorem 13.

Let $G$ be a graph and $L$ be a list-assignment for $G$ with $|L(v)|\geq 2d(v)+1$ for all $v\in V(G)$ . If $\alpha$ and $\beta$ are $L$ -colourings of $G$ , then we can recolour $G$ from $\alpha$ to $\beta$ in at most $n(G)+\mu(G)$ steps.

Proof.

We refer to $V_{1}(G)$ , $V_{2}(G)$ , and $V_{3}(G)$ , as defined in Theorem 12. Starting from $\alpha$ , recolour each vertex $v\in V_{2}(G)$ to avoid each colour used currently on $N(v)$ and also to avoid each colour used on $N(v)$ in $\beta$ ; call the resulting colouring $\tilde{\alpha}(G)$ . Let $G^{\prime}:=G-V_{2}(G)$ . For each $v\in V(G^{\prime})$ , let $L^{\prime}(v):=L(v)\setminus(\cup_{w\in N(v)\cap V_{2}(G)}\tilde{\alpha}(w))$ . Note that $|L^{\prime}(v)|\geq 2d_{G^{\prime}}(v)+1$ . Thus, for each component $H$ of $G^{\prime}$ , we can recolour $H$ from $\alpha$ to $\beta$ in at most $\lfloor 3n(H)/2\rfloor$ steps, by Lemma 11. Finally, we recolour each vertex of $V_{2}(G)$ to its colouring $\beta$ . Let $\operatorname{comp}(G^{\prime})$ denote the set of components of $G^{\prime}$ . The number of recolouring steps used is at most $2|V_{2}(G)|+\sum_{H\in\operatorname{comp}(G^{\prime})}\lfloor 3n(H)/2\rfloor=2|V_{2}(G)|+\frac{3}{2}(|V(G)|-|V_{2}(G)|)-\frac{1}{2}c(V_{1}(G))=|V(G)|+\frac{1}{2}(|V(G)|-c(V_{1}(G))+|V_{2}(G)|)=|V(G)|+\mu(G)$ . The final equality uses Theorem 12(4). The first equality uses that the vertices of a component $H\in\operatorname{comp}(G^{\prime})$ are contained either in $V_{1}(G)$ or in $V_{3}(G)$ . If $V(H)\subseteq V_{3}(G)$ then $n(H)$ is even by Theorem 12(3). On the other hand, if $V(H)\subseteq V_{1}(G)$ then $n(H)$ is odd by Theorem 12(2). ∎

By the comment after Proposition 2, Theorem 13 is sharp. For (non-list) colouring, we get the following.

Corollary 14.

For every graph $G$ and every $k\geq 2\Delta(G)+1$ , we have $\operatorname{diam}\mathcal{C}_{k}(G)=n(G)+\mu(G)$ .

Proof.

The upper and lower bounds follow, respectively, from Theorem 13 and Proposition 1. ∎

4 Proving the Main Results for Correspondences

In this section, we prove the correspondence colouring portions of our main results: Theorems 1(ii) and 2(ii).

Theorem 15.

Let $G$ be a graph and $(L,H)$ be a correspondence cover with $|L(v)|\geq 2d(v)+1$ for all $v\in V(G)$ . If $\alpha$ and $\beta$ are $(L,H)$ -colourings of $G$ , then $G$ can be recoloured from $\alpha$ to $\beta$ in at most $n(G)+\tau(G)$ steps.

Proof.

Let $S$ be a minimum vertex cover. For every vertex $v\in S$ , we recolour $v$ with a colour that, for every $w\in N(v)$ , conflicts (under cover $(L,H)$ ) with neither the current colour $\gamma(w)$ nor the final colour $\beta(w)$ . This is possible because $|L(v)|\geq 2d(v)+1$ . Now we recolour every vertex $v\in V(G)\backslash S$ with $\beta(v)$ and then do this also for every vertex in $S$ . Note that we use at most $n(G)+\tau(G)$ recolourings. ∎

Theorem 16.

Let $G$ be a graph and $(L,H)$ be a correspondence cover for $G$ such that $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ . If $\alpha$ and $\beta$ are $(L,H)$ -colourings of $G$ , then we can recolour $G$ from $\alpha$ to $\beta$ in at most $n(G)+2\tau(G)$ steps.

Proof.

We use induction on $\tau(G)$ . If $\tau(G)=0$ , i.e., $G$ is an independent set, then we simply recolour every vertex $v$ to $\beta(v)$ . So assume the theorem is true for all graphs $G^{\prime}$ with $0\leq\tau(G^{\prime})<\tau(G)$ .

Let $S$ be a minimum vertex cover of $G$ and pick $v\in S$ . Consider the union over all $w\in N(v)$ of the edges in $H$ from $\alpha(w)$ and $\beta(w)$ to $L(v)$ . By Pigeonhole, since $2d(v)<2|L(v)|$ , some colour $c\in L(v)$ has at most one incident edge in this union. (We handle the case when $c$ has exactly one incident edge, since the other case is easier.) Assume there exists $w_{0}\in N(v)$ such that $\alpha(w_{0})$ is matched to $c$ and no other $\alpha(w)$ or $\beta(w)$ is matched to $c$ . (If instead $\beta(w_{0})$ is matched to $c$ , then we swap the roles of $\alpha$ and $\beta$ .) Form $\tilde{\alpha}$ from $\alpha$ by first recolouring $w_{0}$ with a colour different from $\alpha(w_{0})$ , that still gives a proper $(L,H)$ -colouring, and afterward recolouring $v$ with $c$ . Let $G^{\prime}:=G-v$ . For every $w\in N(v)$ , remove from $L(w)$ the colour $c^{\prime}$ matched with $c$ ; call the resulting correspondence cover $(L^{\prime},H^{\prime})$ . Denote the restrictions to $G^{\prime}$ of $\tilde{\alpha}$ and $\beta$ by $\tilde{\alpha}^{\prime}$ and $\beta^{\prime}$ . By induction, since $\tau(G^{\prime})<\tau(G)$ , we can recolour $G^{\prime}$ from $\tilde{\alpha}^{\prime}$ to $\beta^{\prime}$ in at most $n(G^{\prime})+2\tau(G^{\prime})$ steps. After this, we can finish by recolouring $v$ with $\beta(v)$ . Thus, $\operatorname{dist}_{(L,H)}(\alpha,\beta)\leq 2+\operatorname{dist}_{(L^{\prime},H^{\prime})}(\tilde{\alpha}^{\prime},\beta^{\prime})+1\leq 2+n(G^{\prime})+2\tau(G^{\prime})+1=2+n(G)-1+2(\tau(G)-1)+1=n(G)+2\tau(G)$ . This proves the theorem. ∎

5 Distances in Reconfiguration Graphs of Trees

For each tree $T$ , it is straightforward to check that reconfiguration of correspondence colouring is no harder than reconfiguration of list colouring. Given a tree $T$ and a correspondence cover $(L,H)$ , it is easy to construct a list-assignment $L^{\prime}$ for $T$ such that $L^{\prime}$ -colourings of $T$ are in bijection with $(L,H)$ -colourings of $T$ . We can do this by induction on $n(G)$ , by deleting a leaf $v$ and extending the list-assignment $L^{\prime}$ , given by hypothesis, for $T-v$ . So, for simplicity, we phrase all results in this section only in terms of list colourings.

Theorem 17.

Fix a tree $T$ and a list-assignment $L$ with $\lvert L(v)\rvert\geq d(v)+2$ for every $v\in V(T).$ If $\alpha$ and $\beta$ are proper $L$ -colourings of $T$ , then the distance between $\alpha$ and $\beta$ in the reconfiguration graph $\mathcal{C}_{L}(T)$ is equal to $\mu(D_{\alpha,\beta})+\sum_{v\in V}\mathbf{1}_{\alpha(v)\not=\beta(v)}.$

Proof.

The lower bound holds by Observation 5. Now we prove that this lower bound is also an upper bound.

We use induction on $n(T)$ . The base case, $n(T)=1$ , is trivial. Assume the theorem is true whenever $T$ has order at most $s-1$ . We will prove it for an arbitrary tree $T$ on $s$ vertices. If $\alpha(v)=\beta(v)$ for some $v\in V(T)$ , then we use induction on the components of $T-v$ , with $\alpha(v)$ removed from the lists of the neighbours of $v$ .

Suppose instead there are neighbours $v$ and $w$ for which $\overrightarrow{vw}\not\in A(D_{\alpha,\beta})$ . Now $T-vw$ has two components; so let $C_{v}$ and $C_{w}$ be the components, respectively, containing $v$ and $w$ . By deleting $\alpha(w)$ from $L(v)$ , we can first recolour $C_{v}$ . Afterwards, we delete $\beta(v)$ from $L(w)$ and recolour $C_{w}$ . By using the induction hypothesis (twice), we get the desired upper bound, since $\mu(D_{\alpha,\beta})=\mu(D_{\alpha,\beta}[C_{v}])+\mu(D_{\alpha,\beta}[C_{w}]).$

In the remaining case, we have two colour classes, say with colours $1$ and $2$ , which need to be swapped. We pick a smallest vertex cover $S$ , which has size $\tau(D_{\alpha,\beta})=\mu(D_{\alpha,\beta}).$ Iteratively, we recolour every vertex $v$ in $S$ with a colour different from $1$ , $2$ , and all colours used to recolour neighbours of $v$ in $S$ . Note that $v$ has at most $d(v)-1$ neighbours in $S$ , since otherwise $S$ would not be a minimal vertex cover. Since $\lvert L(v)\rvert\geq d(v)+2$ , we can recolour as desired. Next, for each $w\in V(T)\setminus S$ , we recolour $w$ with $\beta(w).$ Finally, we recolour each $v\in S$ with $\beta(v)$ . This proves the induction step, which finishes the proof. ∎

Corollary 18.

If $T$ is a tree and $L$ is a list-assignment with $\lvert L(v)\rvert\geq d(v)+2$ for every $v\in V(T)$ , then

\operatorname{diam}\mathcal{C}_{L}(T)\leq n(T)+\mu(T)\leq\lfloor 3n(T)/2\rfloor.

Proof.

Theorem 17 implies that $\operatorname{diam}~{}\mathcal{C}_{L}(T)\leq n(T)+\mu(T)$ , and the bound $\mu(T)\leq\lfloor\frac{n(T)}{2}\rfloor$ holds trivially, since each edge of a matching saturates two vertices. ∎

Recall that $[k]$ denotes $\{1,\ldots,k\}$ . Thus, we write $[k]$ -colouring to mean a $k$ -colouring from the colours $[k]$ .

Proposition 5.

For every tree $T$ and $k\geq\Delta(T)+2$ , we have

\operatorname{diam}\mathcal{C}_{k}(T)=n(T)+\mu(T)\mbox{ and }\operatorname{rad}\mathcal{C}_{k}(T)\geq n(T)+\left\lceil\frac{\mu(T)}{2}\right\rceil.

Proof.

The inequality $\operatorname{diam}\mathcal{C}_{k}(T)\leq n(T)+\mu(T)$ holds by Corollary 18; and this inequality actually holds with equality, since the two $[2]$ -colourings of $T$ are at distance exactly $n(T)+\mu(T)$ . That is, $\operatorname{diam}\mathcal{C}_{k}(T)=n(T)+\mu(T)$ . Now we consider $\operatorname{rad}\mathcal{C}_{k}(T)$ . If we contract all edges of a maximum matching $M$ in $T$ , the result is also a tree, $T^{\prime}$ . When we 2-colour $T^{\prime}$ , one colour is used on at least half of the contracted edges. Denote the set of these contracted edges by $E^{\prime}$ . Note that $E^{\prime}$ is an induced matching in $T$ . Fix an arbitrary proper $k$ -colouring $\alpha$ of $T$ . Now we construct a proper $k$ -colouring $\beta$ of $T$ by swapping the colours on the endpoints of each edge $vw\in E^{\prime}$ , i.e., let $\beta(v):=\alpha(w)$ and $\beta(w):=\alpha(v)$ for every edge $vw\in E^{\prime}.$ For every vertex $v$ not belonging to an edge in $E^{\prime}$ , choose a colour in $[k]$ different from the colours already assigned (in $\beta$ ) to neighbours of $v$ and different from $\alpha(v).$ Now $\operatorname{dist}(\alpha,\beta)\geq n(T)+\lvert E^{\prime}\rvert\geq n(T)+\left\lceil\frac{\mu(T)}{2}\right\rceil$ by Theorem 17. ∎

We construct trees $T$ for which certain colourings are more “central” in the reconfiguration graph than others. That is, we construct trees $T$ for which $\operatorname{rad}\mathcal{C}_{k}(T)\not=\operatorname{diam}\mathcal{C}_{k}(T)$ . We also study the maximum possible diameter and minimum possible radius of reconfiguration graphs of trees of given order, and the maximum possible difference of these quantities.

Proposition 6.

For every $k\geq 4$ , the path $P_{n}$ satisfies

\operatorname{diam}\mathcal{C}_{k}(P_{n})=\left\lfloor\frac{3n}{2}\right\rfloor\mbox{ and }\operatorname{rad}\mathcal{C}_{k}(P_{n})=\left\lceil\frac{4n-1}{3}\right\rceil.

Furthermore, there exist $n$ -vertex trees $T$ , with maximum degree 3, such that for every $k\geq 5$ we have

\operatorname{diam}\mathcal{C}_{k}(T)=\left\lfloor\frac{3n}{2}\right\rfloor\mbox{ and }\operatorname{rad}\mathcal{C}_{k}(T)=\left\lceil\frac{5n-1}{4}\right\rceil.

All such $T$ maximise, over all $n$ -vertex trees, the difference $\operatorname{diam}\mathcal{C}_{k}(T)-\operatorname{rad}\mathcal{C}_{k}(T)$ .

Proof.

Consider $P_{n}$ with vertex set $\{v_{1},v_{2},\ldots,v_{n}\}$ . Fix $k\geq 4$ , and let $\alpha$ and $\beta$ be the colourings with ranges $[3]$ and $[2]$ , respectively, such that

\alpha(v_{i})\equiv i\ (\mathrm{mod}\ 3)\mbox{~{}~{}~{} and~{}~{}~{} }\beta(v_{i})\equiv i\ (\mathrm{mod}\ 2)~{}~{}~{}~{}~{}\forall i\in[n].

Note that $\operatorname{ecc}(\beta)=\lfloor\frac{3n}{2}\rfloor$ by Theorem 17, since switching colours $1$ and $2$ in $\beta$ requires $\left\lfloor\frac{3n}{2}\right\rfloor$ recolouring steps. Furthermore, Corollary 18 implies that $\operatorname{diam}\mathcal{C}_{k}(P_{n})=\operatorname{ecc}(\beta)=\lfloor\frac{3n}{2}\rfloor$ . On the other hand, for every proper colouring $\gamma$ , we know that $D_{\alpha,\gamma}$ cannot have a pair of bidirected edges of the form $v_{i}v_{i+1}$ and $v_{i+2}v_{i+3},$ since $\alpha(v_{i})=\alpha(v_{i+3}).$ So $\mu(D_{\alpha,\gamma})\leq\lceil\frac{n-1}{3}\rceil$ ; hence, $\operatorname{ecc}(\alpha)\leq n+\lceil\frac{n-1}{3}\rceil$ , which implies that $\operatorname{rad}\mathcal{C}_{k}(P_{n})\leq\lceil\frac{4n-1}{3}\rceil$ .

Next we prove the lower bound on $\operatorname{rad}\mathcal{C}_{k}(P_{n})$ . For every colouring $\alpha$ of $P_{n}$ , we can choose at least $\lceil\frac{n-1}{3}\rceil$ disjoint edges such that swapping the colours in $\alpha$ on the endpoints of each edge (and possibly recolouring vertices not in any of these edges) yields another proper colouring. To see this, first select edge $v_{1}v_{2}.$ Whenever $v_{i}v_{i+1}$ has been selected, there exists $j\in\{i+3,i+4\}$ for which $\alpha(v_{i})\not=\alpha(v_{j})$ . Now add edge $v_{j-1}v_{j}$ to the set of selected edges. When our selection ends, the set $E^{\prime}$ contains at least $\lceil\frac{n-1}{3}\rceil$ edges. We can now construct a $[k]$ -colouring $\beta$ where $\beta(w)=\alpha(v)$ and $\beta(v)=\alpha(w)$ for every edge $vw\in E^{\prime}$ , and $\beta(v)\neq\alpha(v)$ for every $v\in V(P_{n}).$ Theorem 17 gives $\operatorname{dist}(\alpha,\beta)\geq n+\lceil\frac{n-1}{3}\rceil$ .

Now let $T_{n}$ be the $n$ -vertex comb graph; see Figure 3. Here $T_{n}$ is formed from a path $v_{1}v_{2}\ldots v_{t}$ , where $t=\lceil\frac{n}{2}\rceil$ , by adding, for each $v_{i}$ (except $v_{t}$ when $n$ is odd), an additional neighbour $w_{i}$ . Since $\mu(T_{n})=\left\lfloor\frac{n}{2}\right\rfloor$ , by Proposition 5 the diameter of $\mathcal{C}_{k}(T_{n})$ is $\lfloor\frac{3n}{2}\rfloor$ . Let $\alpha$ be the colouring shown and described in Figure 3.

Figure 3: The comb graph

T_{16}

with colouring

\alpha

. The shaded region denotes four edges no two of which, for any colouring

\beta

, yield disjoint bidirected edges of

D_{\alpha,\beta}

For any proper colouring $\beta$ of $T_{n}$ , note that $\mu(D_{\alpha,\beta})\leq\left\lceil\frac{n-1}{4}\right\rceil$ . This holds because, for each odd $i$ , the subgraph $D_{\alpha,\beta}[\{v_{i},v_{i+1},v_{i+2},w_{i},w_{i+1}\}]$ contains no two disjoint bidirected edges. Thus, $\operatorname{ecc}(\alpha)\leq\left\lceil\frac{5n-1}{4}\right\rceil$ , by Theorem 17. Since $\mu(T_{n})=\left\lfloor\frac{n}{2}\right\rfloor$ , Proposition 5 implies that $\operatorname{rad}\mathcal{C}_{k}(T_{n})=n+\left\lceil\left\lfloor n/2\right\rfloor/2\right\rceil=\left\lceil\frac{5n-1}{4}\right\rceil$ . Thus, $\operatorname{diam}\mathcal{C}_{k}(T_{n})-\operatorname{rad}\mathcal{C}_{k}(T_{n})=\left\lfloor\frac{3n}{2}\right\rfloor-\left\lceil\frac{5n-1}{4}\right\rceil=\left\lfloor\frac{n}{4}\right\rfloor$ . For every $n$ -vertex tree $T$ , Proposition 5 implies that $\operatorname{diam}\mathcal{C}_{k}(T)-\operatorname{rad}\mathcal{C}_{k}(T)\leq(n+\mu(T))-(n+\left\lceil\frac{\mu(T)}{2}\right\rceil)=\left\lfloor\frac{\mu(T)}{2}\right\rfloor\leq\left\lfloor\frac{n}{4}\right\rfloor$ . Thus, $T_{n}$ maximises this difference. ∎

For list colourings, the difference $\operatorname{diam}\mathcal{C}_{L}(T)-\operatorname{rad}\mathcal{C}_{L}(T)$ can be even larger.

Proposition 7.

For every tree $T$ , there exists a list-assignment $L$ , with $\lvert L(v)\rvert\geq d(v)+2$ for all $v\in V(T)$ , such that $\operatorname{diam}\mathcal{C}_{L}(G)=n(T)+\mu(T)$ and $\operatorname{rad}\mathcal{C}_{L}(G)=n(T)$ . These values are, respectively, the maximum and minimum possible over all such list-assignments $L$ .

Proof.

Choose a maximum matching $M$ of $T$ and fix $L$ such that

\lvert L(v)\cap L(w)\rvert=\left.\begin{cases}0,&\text{when }vw\not\in M\\ 2,&\text{when }vw\in M.\end{cases}\right.

Let $\alpha$ and $\beta$ be $L$ -colourings such that, for every edge $vw\in M$ , we have $\alpha(v)=\beta(w)$ and $\alpha(w)=\beta(v)$ . For every vertex $v$ not saturated by $M$ , we pick $\alpha(v)$ and $\beta(v)$ to be arbitrary distinct colours in $L(v)$ . By Theorem 17, we have $\operatorname{dist}(\alpha,\beta)=n(T)+\mu(T)$ . Corollary 18 implies that $\operatorname{diam}\mathcal{C}_{L}(T)=n(T)+\mu(T)$ . Further, this diameter is the maximum possible over all such list-assignments $L$ .

To show that $\operatorname{rad}\mathcal{C}_{L}(T)\leq n(T)$ , we construct an $L$ -colouring $\gamma$ such that $\operatorname{dist}(\gamma,\delta)\leq n(T)$ for every $L$ -colouring $\delta$ . Since $|L(v)\setminus\left(\cup_{w\in N(v)}L(w)\right)|\geq 3-2=1$ for every vertex $v$ , we can form an $L$ -colouring $\gamma$ such that every $v\in V(T)$ satisfies $\gamma(v)\notin\cup_{w\in N(v)}L(w)$ . For every proper colouring $\delta$ , by our construction of $\gamma$ , we can recolour $\delta$ into $\gamma$ greedily; hence, $\operatorname{dist}(\delta,\gamma)\leq n(T)$ .

Now we show that $\operatorname{rad}C_{L}(T)\geq n(T)$ . For every $L$ -colouring $\gamma$ , there exists an $L$ -colouring $\delta$ such that $\delta(v)\neq\gamma(v)$ for all $v$ . To see this, let $L^{\prime}(v):=L(v)\setminus\gamma(v)$ . Since $|L^{\prime}(v)|\geq d(v)+1$ for all $v$ , we form $\delta$ by colouring $G$ greedily (in any order) from $L^{\prime}$ . Clearly, $\operatorname{dist}(\gamma,\delta)\geq n(G)$ . Thus, $\operatorname{rad}\mathcal{C}_{L}(T)=n(T)$ . In fact, this lower bound does not depend on the specific choice of $L$ , but only uses that $|L(v)|\geq d(v)+2$ for all $v$ . Thus, this radius is the minimum over all such list-assignments $L$ . ∎

6 Proving the List Conjecture for Complete Bipartite Graphs and Cactuses

A cactus is a connected graph in which each edge lies on at most one cycle. In this section, we prove the List Conjecture for all complete bipartite graphs and for all cactuses. Both proofs are by induction, and rely on the following helpful lemma.

Lemma 19.

Fix a positive integer $b$ . Let $G=(V,E)$ be a graph for which there exists a list-assignment $L$ and two proper $L$ -colourings $\alpha,\beta$ such that $\lvert L(v)\rvert\geq d(v)+b$ for every $v\in V(G)$ , and $\operatorname{dist}_{L}(\alpha,\beta)>n(G)+\mu(G)$ , but, for every proper induced subgraph of $G$ , no such list-assignment exists. Now for every partition $V(G)=V_{1}\cup V_{2}$ into two non-empty subsets of vertices, $D_{\alpha,\beta}$ has at least one arc from $V_{1}$ to $V_{2}$ and at least one arc from $V_{2}$ to $V_{1},$ i.e., $D_{\alpha,\beta}$ is strongly connected.

Proof.

Assume the lemma is false; by symmetry, assume $D_{\alpha,\beta}$ has no arcs from $V_{1}$ to $V_{2}$ . Let $G_{1}:=G[V_{1}]$ and $G_{2}:=G[V_{2}]$ . Let $\gamma$ be the $L$ -colouring where $\gamma(v):=\beta(v)$ when $v\in V_{1}$ and $\gamma(v):=\alpha(v)$ when $v\in V_{2}$ .

For every $v\in V_{1}$ , let $L^{\prime}(v):=L(v)\backslash\{\alpha(w)\mid w\in N(v)\cap V_{2}\}$ . Note that $\lvert L^{\prime}(v)\rvert\geq d_{G_{1}}(v)+b$ . Also note that still $\gamma(v)\in L^{\prime}(v)$ for every $v\in V_{1}$ ; this is where we use that there is no arc from $V_{1}$ to $V_{2}$ . Since $G_{1}$ is a proper induced subgraph of $G$ , by hypothesis $\operatorname{diam}\mathcal{C}_{L^{\prime}}(G_{1})\leq n(G_{1})+\mu(G_{1})$ ; thus $\operatorname{dist}_{L}(\alpha,\gamma)\leq n(G_{1})+\mu(G_{1})$ . Now for every $v\in V_{2}$ , let $L^{\prime}(v):=L(v)\backslash\{\beta(w)\mid w\in N(v)\cap V_{1}\}$ . Similarly to before, $\lvert L^{\prime}(v)\rvert\geq d_{G_{2}}(v)+b$ , so $\operatorname{diam}\mathcal{C}_{L^{\prime}}(G_{2})\leq n(G_{2})+\mu(G_{2})$ ; thus $\operatorname{dist}_{L}(\gamma,\beta)\leq n(G_{2})+\mu(G_{2})$ . By the bounds above and the triangle inequality, we have

	$\displaystyle\operatorname{dist}_{L}(\alpha,\beta)$	$\displaystyle\leq\operatorname{dist}_{L}(\alpha,\gamma)+\operatorname{dist}_{L}(\gamma,\beta)$
		$\displaystyle\leq n(G_{1})+\mu(G_{1})+n(G_{2})+\mu(G_{2})$
		$\displaystyle\leq n(G)+\mu(G).$

The last step uses that the union of a matching in $G_{1}$ and a matching in $G_{2}$ is a matching in $G$ . So $G$ is not a counterexample, and the lemma is true. ∎

It is helpful to note that an analogous statement holds for correspondence colouring. In fact, its proof is nearly identical to that given above. We use this observation in our proof of Theorem 27.

Using Lemma 19, we prove that the List Conjecture holds for all complete bipartite graphs.

Theorem 20.

The List Conjecture is true for all complete bipartite graphs.

Proof.

Suppose the theorem is false and choose a counterexample $K_{p,q}$ minimizing $p+q$ . By symmetry, we assume that $p\leq q$ . Denote the parts of $G$ by $U$ and $W$ , with $|U|=p$ and $|W|=q$ .

By Lemma 19, we have $\alpha(U)\subseteq\beta(W)$ and $\alpha(W)\subseteq\beta(U)$ . By swapping the roles of $\alpha$ and $\beta$ , we also have $\beta(U)\subseteq\alpha(W)$ and $\beta(W)\subseteq\alpha(U)$ ; thus, $\alpha(U)=\beta(W)$ and $\alpha(W)=\beta(U)$ . Note that $\alpha(U)\cap\beta(U)=\alpha(U)\cap\alpha(W)=\emptyset$ , because the graph is complete bipartite.

Case 1: $\bm{|W|\geq|\alpha(U)|+|\beta(U)|-1}$ . For each $u\in U$ , we have $|L(u)|\geq|W|+2\geq|\alpha(U)|+|\beta(U)|+1=|\beta(W)|+|\alpha(W)|+1$ . First recolour each $u\in U$ from $L(u)\setminus(\alpha(W)\cup\beta(W))$ . Now recolour each $w\in W$ with $\beta(w)$ . Finally, recolour each $u\in U$ with $\beta(u)$ . The number of steps that we use is at most $2|U|+|W|=n(G)+\mu(G)$ .

Case 2: $\bm{|W|\leq|\alpha(U)|+|\beta(U)|-2}$ . If $|W|\geq 2|\alpha(U)|$ and $|W|\geq 2|\beta(U)|$ , then $2|W|\geq 2|\alpha(U)|+2|\beta(U)|$ , which contradicts the case. So assume, by symmetry, that $|W|\leq 2|\beta(U)|-1$ ; if not, then simply interchange the roles of $\alpha$ and $\beta$ . Now, by Pigeonhole, there exists $c\in\beta(U)$ such that $|\alpha^{-1}(c)|=|\alpha^{-1}(c)\cap W|\leq 1$ . So, recolour $w\in\alpha^{-1}(c)$ , if such $w$ exists, to avoid $\alpha(U)\cup\{c\}$ , and then recolour every $u\in\beta^{-1}(c)$ with $c$ . Now we delete every $u$ such that $\beta(u)=c$ , we delete $c$ from $L(w)$ for every $w\in W$ , and we finish on the resulting smaller graph $G_{2}$ (with an assignment of smaller lists) by the minimality of $G$ . In total, the number of recolouring steps we use is at most $|\alpha^{-1}(c)|+|\beta^{-1}(c)|+|V(G_{2})|+\mu(G_{2})\leq|\alpha^{-1}(c)|+|\beta^{-1}(c)|+(n(G)-|\beta^{-1}(c)|)+(\mu(G)-|\beta^{-1}(c)|)\leq n(G)+\mu(G)$ . ∎

Using Lemma 19, we prove that the List Conjecture holds for all cycles.

Lemma 21.

Let $G$ be a cycle $v_{1}v_{2}\cdots v_{n}$ and $L$ be a list-assignment such that, for all $v_{i}$ , we have $\lvert L(v_{i})\rvert\geq 4$ . If $\alpha$ and $\beta$ are proper $L$ -colourings of $G$ , then we can recolour $G$ from $\alpha$ to $\beta$ in at most $\lfloor 3n/2\rfloor$ steps.

Proof.

By Lemma 19, with $b=2$ , if $\operatorname{dist}(\alpha,\beta)>\lfloor 3n/2\rfloor$ , then $D_{\alpha,\beta}$ is strongly connected. This implies that $D_{\alpha,\beta}$ contains a directed cycle $C_{n}$ as a subdigraph. (If $D_{\alpha,\beta}$ contains a bidirected path $P$ , then $|\alpha(V(P))\cup\beta(V(P))|=2$ . So, if $P$ is spanning, then its order must be even, to avoid a conflict between the colours of its endpoints. But then $D_{\alpha,\beta}$ contains an additional arc, so $D_{\alpha,\beta}$ contains a directed cycle, as claimed.)

If $D_{\alpha,\beta}$ is a bidirected cycle, then $n$ must be even, as in the previous paragraph, and $\frac{3n}{2}$ recolouring steps suffice. Suppose instead that $D_{\alpha,\beta}$ is precisely a directed cyle. When $n=3$ , we recolour one vertex $v$ in a colour absent from $\alpha(V(G))\cup\beta(V(G))$ , recolour the other two vertices in order (to match $\beta$ ), and finally recolour $v$ with $\beta(v)$ . When $n\geq 4$ , we recolour one vertex $v$ in a colour absent from $\alpha(v)\cup\alpha(N(v))$ . Now we can recolour correctly (in order) all vertices of $G$ except for $v$ and one of its neighbours. Correctly colouring these final two vertices takes at most 3 recolouring steps. Now we are done, since $1+(n-2)+3\leq\lfloor 3n/2\rfloor$ .

In the remaining case, we have $n\geq 4$ and some directed edge is adjacent to a bidirected edge. Without loss of generality, we assume $\overrightarrow{v_{1}v_{2}},\overrightarrow{v_{2}v_{3}},\overrightarrow{v_{2}v_{1}}\in A(D_{\alpha,\beta})$ but $\overrightarrow{v_{3}v_{2}}\notin A(D_{\alpha,\beta})$ . Recolour $v_{1}$ with a colour $c$ different from $\alpha(v_{1})$ , $\alpha(v_{2})$ , and $\alpha(v_{n})$ . Now delete $c$ from $L(v_{2})$ and $L(v_{n})$ , and let $G^{\prime}:=G-v_{1}$ . By Theorem 17, we can recolour $G^{\prime}$ from $\alpha$ to $\beta$ (both restricted to $G^{\prime}$ ) using at most $(n-1)+\left\lfloor\frac{n-2}{2}\right\rfloor$ recolouring steps. Here we use that $\overrightarrow{v_{3}v_{2}}$ is not an arc, so $\mu(D_{\alpha,\beta}[V(G^{\prime})])\leq\left\lfloor\frac{n-2}{2}\right\rfloor$ . Finally, we recolour $v_{1}$ with $\beta(v_{1})$ . ∎

Using Lemmas 19 and 21, we can prove that the List Conjecture is true for every cactus.

Theorem 22.

The List Conjecture is true for every cactus.

Proof.

Instead assume the theorem is false. Let $G$ be a counterexample minimizing $n(G)$ and let $\alpha$ and $\beta$ be $L$ -colourings with $\operatorname{dist}(\alpha,\beta)>n(G)+\mu(G)$ . Every proper induced subgraph $H$ of $G$ is a disjoint union of cactuses, say $H_{1},\ldots,H_{r}$ ; since $n(H)=\sum_{i=1}^{r}n(H_{i})$ and $\mu(H)=\sum_{i=1}^{r}\mu(H_{i})$ , the List Conjecture must hold for $H$ , by the minimality of $G$ . Lemma 19 implies that $D_{\alpha,\beta}$ is strongly connected. And Lemma 21 implies that $G$ is not a cycle. The following claim restricts the structure of $G$ , $\alpha$ , and $\beta$ .

Claim 23.

If $v\in V(G)$ and $\mu(G-v)=\mu(G)-1$ , then $L(v)\subseteq\cup_{w\in N(v)}\{\alpha(w),\beta(w)\}$ . In particular, each block of $G$ containing $v$ gives rise to exactly two arcs in $D_{\alpha,\beta}$ incident to $v$ , and $v$ has no adjacent leaf in $G$ .

Proof.

Instead assume there exists $c\in L(v)\setminus\cup_{w\in N(v)}\{\alpha(w),\beta(w)\}$ . Recolour $v$ with $c$ , let $G^{\prime}:=G-v$ , let $L^{\prime}(w):=L(w)\setminus\{c\}$ for all $w\in N(v)$ , and otherwise let $L^{\prime}(w):=L(w)$ . Denote by $\alpha^{\prime}$ and $\beta^{\prime}$ the restrictions to $G^{\prime}$ of $\alpha$ and $\beta$ . Since $G$ is minimal, we can recolour $G^{\prime}$ from $\alpha^{\prime}$ to $\beta^{\prime}$ , using $L^{\prime}$ , in at most $n(G^{\prime})+\mu(G^{\prime})=n(G)-1+\mu(G)-1$ recolouring steps. We finish by recolouring $v$ with $\beta(v)$ . This proves the first statement.

Since $D_{\alpha,\beta}$ is strongly connected, each block $B$ of $G$ containing $v$ gives rise to at least two arcs in $D_{\alpha,\beta}$ incident to $v$ , one in each direction. Since $G$ is a cactus, each such $B$ contains at most 2 neighbours of $v$ . So at least half of the neighbours of $v$ are coloured $\beta(v)$ by $\alpha$ , and also at least half of the neighbours of $v$ are coloured $\alpha(v)$ by $\beta$ . Therefore $|\cup_{w\in N(v)}\{\alpha(w),\beta(w)\}|\leq 2\cdot(d(v)/2+1))=d(v)+2$ . If any such $B$ is either $K_{2}$ or gives rise to at least three arcs in $D_{\alpha,\beta}$ incident with $v$ , then $|\cup_{w\in N(v)}\{\alpha(w),\beta(w)\}|\leq d(v)+1<\lvert L(v)\rvert$ , which contradicts the first statement. This proves the second statement. ∎

It is easy to check that every neighbour $v$ of a leaf $w$ in $G$ satisfies $\mu(G-v)=\mu(G)-1$ . Thus, Claim 23 implies that $G$ has no leaf vertex. This implies that all endblocks of $G$ are cycles. Let $C_{s}$ be an endblock. Denote its vertices by $w_{1},\ldots,w_{s}$ , such that $w_{s}$ is the unique cut-vertex in the block.

Claim 24.

The endblock $C_{s}$ is not an even cycle.

Proof.

Assume instead that $C_{s}$ is an even cycle. It is easy to check that $\mu(G-w_{i})=\mu(G)-1$ whenever $i$ is even. That is, every maximum matching saturates $w_{i}$ whenever $i$ is even. By Claim 23, every $w_{i}$ is incident in $D_{\alpha,\beta}$ to exactly two arcs arising from $C_{s}$ . Since $D_{\alpha,\beta}$ is strongly connected, this implies that $D_{\alpha,\beta}[V(C_{s})]$ is a directed cycle; by symmetry, we assume that it is oriented as $\overrightarrow{w_{s}w_{1}},\overrightarrow{w_{1}w_{2}},\ldots,\overrightarrow{w_{s-1}w_{s}}$ .

We first recolour $w_{s}$ with a colour absent from $\alpha(N[w_{s}])=\left(\cup_{x\in N(w_{s})}\alpha(x)\right)\cup\beta(w_{s-1})$ . Now we recolour each $w_{i}$ to $\beta(w_{i})$ , with $i$ decreasing from $s-1$ to $2$ . Let $G^{\prime}:=G-\{w_{1},\ldots,w_{s-1}\}$ , let $L^{\prime}(w_{s}):=L(w_{s})\setminus\{\alpha(w_{1}),\beta(w_{s-1})\}$ , and otherwise let $L^{\prime}(v):=L(v)$ . Since $G$ is minimal, we can recolour $G^{\prime}$ from its current colouring to $\beta$ (restricted to $G^{\prime}$ ) using at most $n(G^{\prime})+\mu(G^{\prime})\leq(n(G)-(s-1))+(\mu(G)-\frac{s}{2}+1)$ steps. Finally, recolour $w_{1}$ to $\beta(w_{1})$ . The total number of recolouring steps is at most $1+(s-2)+(n(G)-(s-1)+\mu(G)-\frac{s}{2}+1)+1=n(G)+\mu(G)+2-\frac{s}{2}$ . Since $s\geq 4$ , this is at most $n(G)+\mu(G)$ . ∎

Claim 25.

The endblock $C_{s}$ is not an odd cycle.

Proof.

Assume instead that $C_{s}$ is an odd cycle. If $D_{\alpha,\beta}[C_{s}-w_{s}]$ contains fewer than $\left\lfloor\frac{s}{2}\right\rfloor$ disjoint digons (for example, this is true when $s=3$ ), then we can easily finish, as follows. We recolour $w_{s}$ in a colour different from $\alpha(N(w_{s}))\cup\beta(\{w_{1},w_{s-1}\})$ . This is possible because $\beta(w_{s})$ is used by $\alpha$ on at least two neighbours of $w_{s}$ , since $D_{\alpha,\beta}$ is strongly connected. By Theorem 17, we recolour $C_{s}-w_{s}$ to $\beta$ in at most $(s-1)+\left\lfloor\frac{s}{2}\right\rfloor-1$ steps, and we then recolour $G\backslash(C_{s}-w_{s})$ to $\beta$ in at most $n(G)-(s-1)+\mu(G)-\left\lfloor\frac{s}{2}\right\rfloor$ steps. Thus, we recolour $G$ from $\alpha$ to $\beta$ in at most $n(G)+\mu(G)$ steps.

Now we consider the other case, when $w_{i}w_{i+1}$ is a digon of $D_{\alpha,\beta}$ for every odd $i$ with $i<s$ . Since $D_{\alpha,\beta}[C_{s}]$ is strongly connected, we assume $D_{\alpha,\beta}$ contains arc $w_{i}w_{i+1}$ for every $0\leq i\leq s-1$ . Similar to the proof of Lemma 21, here $D_{\alpha,\beta}[C_{s}]$ cannot contain a spanning bidirected path, since $s$ is odd. This implies, for some even $j$ , that $D_{\alpha,\beta}$ does not contain $w_{j+1}w_{j}$ . Now we will recolour some set of $w_{i}$ ’s to reach a new colouring $\tilde{\alpha}$ , such that $D_{\tilde{\alpha},\beta}[C_{s}]$ is either acyclic or contains a single directed cycle, $w_{s-2}w_{s-1}$ . From $\tilde{\alpha}$ , we can recolour $G\setminus(C_{s}-w_{s})$ by the minimality of $G$ , and afterward finish on $C_{s}-w_{s}$ . The details follow.

First suppose that $\beta(w_{s})=\alpha(w_{s-1})$ . For every $i$ such that either (a) $i<j$ and $i$ is odd or (b) $i>j$ and $i$ is even, recolour $w_{i}$ with a colour different from those in $\{\alpha(w_{i-1}),\alpha(w_{i}),\alpha(w_{i+1})\}$ . Here we take the indices modulo $s$ , i.e., $w_{0}=w_{s}$ . If $\beta(w_{s})\neq\alpha(w_{s-1})$ , then we recolour the same set of $w_{i}$ ’s, except for $w_{s-1}$ . Let $G^{\prime}:=G-\{w_{1},\ldots,w_{s-1}\}$ . By the minimality of $G$ , we can recolour $G^{\prime}$ in at most $n(G^{\prime})+\mu(G^{\prime})=(n(G)-(s-1))+(\mu(G)-\left\lfloor\frac{s}{2}\right\rfloor)$ steps. In the case that $\beta(w_{s})\neq\alpha(w_{s-1})$ , we now recolour $w_{s-1}$ with a colour different from those in $\{\alpha(w_{s-2}),\alpha(w_{s-1}),\beta(w_{s})\}$ . For every odd $i$ such that $j+1\leq i\leq s-2$ , we recolour $w_{i}$ with $\beta(w_{i})$ . Next, for every even $i$ such that $2\leq i\leq j$ , we recolour $w_{i}$ with $\beta(w_{i}).$ Finally, the remaining vertices in $C_{s}$ can also be recoloured with their colour in $\beta$ . This process uses at most $n(G)+\mu(G)$ steps. ∎

Recall that every endblock of $G$ is a cycle, as observed following Claim 23. Thus, Claims 24 and 25 yield a contradiction, which proves the theorem. ∎

7 Proving the Correspondence Conjecture for Cactuses, Subcubic Graphs, and Graphs with Low Maximum Average Degree

The maximum average degree of a graph $G$ , denoted $\operatorname{mad}(G)$ , is the maximum, taken over all subgraphs $H$ , of the average degree of $H$ . That is, $\operatorname{mad}(G):=\max_{H\subseteq G}2|E(H)|/|V(H)|$ . Let $d^{1}(v)$ denote the number of neighbours $w$ of $v$ such that $d(w)=1$ . In this section we prove the Correspondence Conjecture for all subcubic graphs, cactuses, and graphs $G$ with $\operatorname{mad}(G)<2.4$ . To do so, we often implicitly use the following observation. We omit its proof, which is easy.

Observation 26.

If $G$ is a graph with a minimum vertex cover $S$ and $v\in S$ , then $\tau(G-v)=\tau(G)-1$ .

Theorem 27.

Let $G$ be a graph and $(L,H)$ a correspondence cover for $G$ such that, for all $v\in V(G)$ we have $|L(v)|\geq d(v)+2$ . Now $\operatorname{diam}\mathcal{C}_{(L,H)}(G)\leq n(G)+\tau(G)$ if at least one of the following holds.

(a)

$\Delta(G)\leq 3$ .
(b)

$G$ is a cactus.
(c)

$\operatorname{mad}(G)<2.4$ .

Proof.

Fix $G$ satisfying (a), (b), or (c) and $(L,H)$ as in the theorem. Fix arbitrary $(L,H)$ -colourings $\alpha$ and $\beta$ . Our proof is by a double induction: primarily on $\tau(G)$ and secondarily on $|V(G)|$ . The base case, $\tau(G)=0$ , is trivial, since $G$ is an independent set and we can greedily recolour $G$ from $\alpha$ to $\beta$ . For the induction step, assume $\tau(G)\geq 1$ .

We first show that $G$ contains either (i) a vertex $v$ such that $d(v)\leq 3$ and $v$ lies in some minimum vertex cover or (ii) a vertex $v$ such that $d(v)\geq 4$ and $d(v)-d^{1}(v)\leq 2$ . Next we show how to proceed by induction in each of cases (i) and (ii).

If $G$ satisfies (a), then clearly $G$ contains an instance of (i). Suppose $G$ satisfies (b), and consider an endblock $B$ of $G$ . If $B$ is a cycle, then $B$ contains adjacent non-cut vertices, $v$ and $w$ ; note that $d(v)=d(w)=2$ . Further, every vertex cover of $G$ contains $v$ or $w$ , so $G$ contains (i). Assume instead that every endblock of $G$ is an edge.

Form a graph $J$ with a vertex for every block in $G$ , where two vertices of $J$ are adjacent if their corresponding blocks share a vertex in $G$ . Now the endpoints of a diameter in $J$ correspond with pendent edges in $G$ . For the leaf $v$ corresponding to such a pendent edge, call its neighbour $w$ . Clearly $w$ lies in some minimum vertex cover of $G$ . If $d(w)\leq 3$ , then $G$ contains (i). Otherwise, $d(w)-d^{1}(w)\leq 2$ , since by the choice of $w$ at most one block incident to $w$ is not an endblock; so $G$ contains (ii). This concludes the case that $G$ satisfies (b).

Assume instead that $G$ satisfies (c). Suppose, to reach a contradiction, that $G$ contains neither (i) nor (ii). Form $G^{\prime}$ from $G$ by deleting all vertices with degree at most 1. We will show that $2|E(G^{\prime})|/|V(G^{\prime})|\geq 2.4$ , a contradiction. Note that $G^{\prime}$ has minimum degree (at least) 2. If an arbitrary vertex $v$ satisfies $d_{G^{\prime}}(v)=2$ , then $d_{G}(v)=2$ , since otherwise $v$ is an instance of (i) or (ii) in $G$ . Further, if $d_{G^{\prime}}(v)=2$ , then $d(w)\geq 3$ for all $vw\in E(G^{\prime})$ , since otherwise $v$ or $w$ is an instance of (i) in $G$ . Now we will reach a contradiction with discharging. Give each vertex $v$ in $G^{\prime}$ charge $\operatorname{ch}(v):=d_{G^{\prime}}(v)$ . We use a single discharging rule: Each 2-vertex in $G^{\prime}$ takes $0.2$ from each neighbour. Now each 2-vertex $v$ in $G^{\prime}$ finishes with charge $\operatorname{ch}^{*}(v)=2+2(0.2)=2.4$ . And each vertex $v$ with $d_{G^{\prime}}(v)\geq 3$ finishes with charge $\operatorname{ch}^{*}(v)\geq d_{G^{\prime}}(v)-0.2d_{G^{\prime}}(v)=0.8d_{G^{\prime}}(v)\geq 2.4$ . This yields the desired contradiction, which proves that $G$ contains either (i) or (ii) if $\operatorname{mad}(G)<2.4$ .

Now we prove the induction step in the cases that $G$ contains (i) or (ii).

Suppose $G$ contains (i). Suppose at most one neighbour, say $w$ , of $v$ has $\alpha(w)$ matched with $\beta(v)$ . Now recolour $w$ with a colour not matched to $\alpha(x)$ , for every $x\in N(w)$ , and not matched to $\beta(v)$ . Next, recolour $v$ with $\beta(v)$ , and proceed on $G-v$ by induction (with the colour matched to $\beta(v)$ deleted from the lists of all vertices in $N(v)$ ). So instead assume there exist at least two such neighbours, say $w_{1}$ and $w_{2}$ . By interchanging the roles of $\alpha$ and $\beta$ (and repeating this argument), we see that also there exist two neighbours, say $x_{1}$ and $x_{2}$ , such that $\beta(x_{1})$ and $\beta(x_{2})$ are matched to $\alpha(v)$ . The total number of colours in $L(v)$ matched to $\alpha(w)$ or $\beta(w)$ for some $w\in N(v)$ is at most $2d(v)-2<d(v)+2$ , since $d(v)\leq 3$ . Hence, there exists $c\in L(v)$ that is not matched to $\alpha(w)$ or $\beta(w)$ for all $w\in N(v)$ . Recolour $v$ with $c$ . Proceed on $G-v$ by induction, with that colour that $c$ is matched to deleted from the list $L(w)$ for each $w\in N(v)$ . After finishing on $G-v$ , recolour $v$ with $\beta(v)$ . The number of steps we use is at most $1+n(G-v)+\tau(G-v)+1=n(G)+\tau(G)$ .

Suppose instead $G$ contains (ii). The proof is almost the same as for (i). If there exists $w\in N(v)$ such that $d(w)=1$ and $\alpha(v)$ is not matched to $\beta(w)$ , then simply recolour $w$ with $\beta(w)$ , and proceed by induction; here we use the secondary induction hypothesis, since possibly $\tau(G-w)=\tau(G)$ . So assume that no such $w$ exists. By interchanging the roles of $\alpha$ and $\beta$ , we also assume that $\beta(v)$ is matched to $\alpha(w)$ for each $w\in N(v)$ with $d(w)=1$ . Further, if $v$ has a non-leaf neighbour $w$ , then at least one such neighbour has $\alpha(v)$ matched to $\beta(w)$ and at least one (possibly the same one) has $\alpha(w)$ matched to $\beta(v)$ . (This follows from the correspondence colouring analog of Lemma 19.) But now there exists $(v,i)\in L(v)$ such that for all $w\in N(v)$ , colour $(v,i)$ is not matched to either $\alpha(w)$ or $\beta(w)$ . Recolour $v$ to $(v,i)$ , and let $G^{\prime}:=G-v$ . Form $(L^{\prime},H)$ from $(L,H)$ by deleting from $L(w)$ , for every $w\in N(v)$ , the colour matched with $(v,i)$ . By induction, we can recolour $G^{\prime}$ from $\alpha$ to $\beta$ (both restricted to $G^{\prime}$ ) using at most $n(G^{\prime})+\tau(G^{\prime})=n(G)+\tau(G)-2$ steps. Finally, recolour $v$ to $\beta(v)$ . This uses at most $n(G)+\tau(G)$ steps, which finishes the proof. ∎

Corollary 28.

The List Conjecture holds for all bipartite graphs $G$ with $\Delta(G)\leq 3$ .

Proof.

When $G$ is bipartite, recall that $\tau(G)=\mu(G)$ . ∎

8 Concluding Remarks

In this paper, we give evidence for both the List Conjecture and the Correspondence Conjecture. We also give evidence for an affirmative answer to Question 1. The List Conjecture and Question 1 would together determine the precise diameter for $\mathcal{C}_{\Delta(G)+2}(G)$ and, as such, a precise bound when Cereceda’s Conjecture is restricted to regular graphs. So we explicitly conjecture the following.

Conjecture 3 (Regular Cereceda’s Conjecture).

For a $d$ -regular graph $G$ , if $k=d+2$ , then $\operatorname{diam}~{}\mathcal{C}_{k}(G)=n(G)+\mu(G)$ .

In Theorem 10 we prove, when $\lvert L(v)\rvert\geq d(v)+2$ for all $v\in V(G)$ , that $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+2\mu(G)\leq 2n(G)$ . In a similar vein, it would be interesting to show that $\operatorname{diam}\mathcal{C}_{L}(G)$ is linear when $\lvert L(v)\rvert\geq\lceil\operatorname{mad}(G)+2\rceil.$ The following conjecture can be viewed as a “balanced” version of the List Conjecture.

Conjecture 4 (Mad Colouring Reconfiguration Conjecture).

For a graph $G$ with $\operatorname{mad}(G)=d$ , if $L$ is a list-assignment such that $\lvert L(v)\rvert\geq\lceil d+2\rceil$ for every $v\in V(G)$ , then $\operatorname{diam}\mathcal{C}_{L}(G)=O_{d}(n).$

Feghali [11] proved that if $\epsilon>0$ and $k\geq d+1+\epsilon$ , then $\operatorname{diam}\mathcal{C}_{k}(G)=O_{d}(n(2\ln{n})^{d})$ . Conjecture 4 aims to prove a similar result for list colouring, with one more colour available for each vertex, and with a somewhat stronger bound on diameter. All planar graphs $G$ have $\operatorname{mad}(G)<6$ , and all triangle-free planar graphs $G$ have $\operatorname{mad}(G)<4$ , so we note that Conjecture 4 would imply stronger forms of [10, Conjecture 22]. If $G$ is regular, then $\operatorname{mad}(G)=\operatorname{degen}(G)$ , so Conjecture 4 is true by Theorem 10. Conjecture 4 is also related to⁴⁴4If $\operatorname{mad}(G)$ is not an integer, then $\operatorname{degen}(G)+3\leq\left\lceil\operatorname{mad}(G)+2\right\rceil$ . But if $G$ has a regular subgraph of degree $\operatorname{mad}(G)$ , then this inequality fails. a conjecture of Bartier et al. [1, Conjecture 1.6] that graphs $G$ with $\operatorname{degen}(G)=d$ satisfy $\operatorname{diam}\mathcal{C}_{d+3}(G)=O_{d}(n)$ .

We do not know if Conjecture 4 might be true with a linear bound of the form $O(n)$ instead of $O_{d}(n).$ But we do note, for this version of the conjecture and every constant $c$ , that no bound of the form $n(G)+c\mu(G)$ can hold. This is shown by the star $K_{1,3c+3}=(\{u\}\cup\{w_{1},\ldots,w_{3c+3}\},E)$ and the colourings $\alpha,\beta$ with $\alpha(u)=1,\beta(u)=4$ , $\beta(w_{i})=1$ and $\alpha(w_{i})=1+\left\lceil i/(c+1)\right\rceil$ . Here $\lceil\operatorname{mad}(G)+2\rceil=4$ and $\operatorname{dist}(\alpha,\beta)>n+c.$

For a correspondence cover $(L,H)$ such that $|L(v)|=d(v)+2$ for all $v\in V(G)$ , in Theorem 1(ii) we proved that $\operatorname{diam}~{}\mathcal{C}_{(L,H)}(G)\leq n(G)+2\tau(G)$ . We view this as modest evidence that Cereceda’s Conjecture might remain true in the more general context of correspondence colourings.

8.1 Open Problems

The three focuses of this paper are the List Conjecture, the Correspondence Conjecture, and (to a lesser extent) Question 1. All of these remain open. However, each of them seems rather hard. So, to motivate further research, below we identify some specific classes of graphs for which we believe that each conjecture may be approachable. We begin with some graph classes for which it would be particularly interesting to make further progress on the List Conjecture.

$(1)$

Complete $r$ -partite graphs for each $r\geq 3$ . (We know the List Conjecture is true for both complete graphs and complete bipartite graphs, so this is a natural common generalization.)
$(2)$

Bipartite graphs, not necessarily complete.
$(3)$

Outerplanar graphs and, more generally, planar graphs.
$(4)$

Subcubic graphs. (We already proved the Correspondence Conjecture for this class; nonetheless, the List Conjecture remains open.)

Conversely, the Correspondence Conjecture remains open for the following basic graph classes.

$(1)$

Complete graphs. (The argument of Bonamy and Bousquet for complete graphs directly yields the List Conjecture, but does not yield the Correspondence Conjecture.)
$(2)$

Complete bipartite graphs.
$(3)$

Bipartite graphs, not necessarily complete. (This would imply the List Conjecture for the same class.)
$(4)$

Outerplanar graphs and, more generally, planar graphs.

Finally, we stress that it will be interesting to improve on Theorems 1 and 2. For example, find the smallest $\epsilon$ such that for every graph $G$ and list-assignment $L$ with $|L(v)|\geq d(v)+2$ for all $v\in V(G)$ , we have $\operatorname{diam}\mathcal{C}_{L}(G)\leq n(G)+(1+\epsilon)\mu(G)$ . We proved $\epsilon=1$ suffices, while $\epsilon=0$ would resolve the List Conjecture.

Acknowledgement

We thank the organisers of the online workshop Graph Reconfiguration of the Sparse Graphs Coalition⁵⁵5For more information, visit https://sparse-graphs.mimuw.edu.pl/doku.php., where this project started. We also thank the two referees for their careful reading and valuable feedback.

References

[1] V. Bartier, N. Bousquet, C. Feghali, M. Heinrich, B. Moore, and T. Pierron. Recoloring planar graphs of girth at least five. SIAM J. Discrete Math., 37(1):332–350, 2023. doi:10.1137/21M1463598.
[2] B. Bollobás, P. A. Catlin, and P. Erdős. Hadwiger’s conjecture is true for almost every graph. European J. Combin., 1(3):195–199, 1980. doi:10.1016/S0195-6698(80)80001-1.
[3] M. Bonamy and N. Bousquet. Recoloring graphs via tree decompositions. European J. Combin., 69:200–213, 2018, arXiv:1403.6386.
[4] P. Bonsma and L. Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoret. Comput. Sci., 410(50):5215--5226, 2009. doi:10.1016/j.tcs.2009.08.023.
[5] N. Bousquet, L. Feuilloley, M. Heinrich, and M. Rabie. Short and local transformations between ( $\Delta$ +1)-colorings. 2022, arXiv:2203.08885.
[6] N. Bousquet and M. Heinrich. A polynomial version of Cereceda’s conjecture. J. Combin. Theory Ser. B, 155:1--16, 2022. doi:10.1016/j.jctb.2022.01.006.
[7] L. Cereceda. Mixing graph colourings. PhD thesis, The London School of Economics and Political Science (LSE), 2007.
[8] L. Cereceda, J. van den Heuvel, and M. Johnson. Connectedness of the graph of vertex-colourings. Discrete Math., 308(5-6):913--919, 2008. doi:10.1016/j.disc.2007.07.028.
[9] M. Delcourt and L. Postle. Reducing linear Hadwiger’s conjecture to coloring small graphs. 2021, arXiv:2108.01633.
[10] Z. Dvořák and C. Feghali. A Thomassen-type method for planar graph recoloring. European J. Combin., 95:Paper No. 103319, 12, 2021. doi:10.1016/j.ejc.2021.103319.
[11] C. Feghali. Reconfiguring colorings of graphs with bounded maximum average degree. J. Combin. Theory Ser. B, 147:133--138, 2021. doi:10.1016/j.jctb.2020.11.001.
[12] M. Jerrum. A very simple algorithm for estimating the number of $k$ -colorings of a low-degree graph. Random Structures Algorithms, 7(2):157--165, 1995. doi:10.1002/rsa.3240070205.
[13] M. Molloy. The list chromatic number of graphs with small clique number. J. Combin. Theory Ser. B, 134:264--284, 2019. doi:10.1016/j.jctb.2018.06.007.
[14] C. M. Mynhardt and S. Nasserasr. Reconfiguration of colourings and dominating sets in graphs. In 50 years of combinatorics, graph theory, and computing, Discrete Math. Appl. (Boca Raton), pages 171--191. CRC Press, Boca Raton, FL, 2020. doi:10.1201/9780429280092-10.
[15] N. Nishimura. Introduction to reconfiguration. Algorithms (Basel), 11(4):Paper No. 52, 25, 2018.
[16] J. van den Heuvel. The complexity of change. In Surveys in combinatorics 2013, volume 409 of London Math. Soc. Lecture Note Ser., pages 127--160. Cambridge Univ. Press, Cambridge, 2013, arXiv:1312.2816.

Optimally Reconfiguring List and Correspondence Colourings

Abstract

1 Introduction

Cereceda’s Conjecture.

Proposition 1.

Proof.

Conjecture 1 (List Colouring Reconfiguration Conjecture).

Conjecture 2 (Correspondence Colouring Reconfiguration Conjecture).

Proposition 2.

Theorem 1.

Theorem 2.

2 Definitions, Notation, and Easy Lower Bounds

Definition 3.

Definition 4.

2.1 Improved Lower Bounds

Observation 5.

Proof.

Example 6.

Proof.

Proposition 2.

Proof.

Example 7.

Proposition 3.

Proof.

Proposition 4.

Proof.

Question 1.

3 Proving the Main Results for Lists

Lemma 8.

Proof.

Corollary 9.

Theorem 10.

Proof.

Lemma 11.

Proof.

Theorem 12 (Edmonds–Gallai Decomposition Theorem).

Theorem 13.

Proof.

Corollary 14.

Proof.

4 Proving the Main Results for Correspondences

Theorem 15.

Proof.

Theorem 16.

Proof.

5 Distances in Reconfiguration Graphs of Trees

Theorem 17.

Proof.

Corollary 18.

Proof.

Proposition 5.

Proof.

Proposition 6.

Proof.

Proposition 7.

Proof.

6 Proving the List Conjecture for Complete Bipartite Graphs and Cactuses

Lemma 19.

Proof.

Theorem 20.

Proof.

Lemma 21.

Proof.

Theorem 22.

Proof.

Claim 23.

Proof.

Claim 24.

Proof.

Claim 25.

Proof.

7 Proving the Correspondence Conjecture for Cactuses, Subcubic Graphs, and Graphs with Low Maximum Average Degree

Observation 26.

Theorem 27.

Proof.

Corollary 28.

Proof.

8 Concluding Remarks

Conjecture 3 (Regular Cereceda’s Conjecture).

Conjecture 4 (Mad Colouring Reconfiguration Conjecture).

Optimally Reconfiguring
List and Correspondence Colourings