# 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_ADDRESS>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_ADDRESS>Daniel W. Cranston Virginia Commonwealth University, Department of Computer
Science<EMAIL_ADDRESS>
###### 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.

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)$.

###### 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)$

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

  2. $(2)$

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

  3. $(3)$

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

  4. $(4)$

$k\geq\Delta(G)+3$ and $G$ is triangle-free, if Reed’s Conjecture111Recall
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. $(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. $(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. $(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. $(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. $(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. $(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. $(1)$

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

  2. $(2)$

true if $G$ is $K_{t+1}$-minor free and $k\geq 2t$, provided Hadwiger’s
Conjecture222Recall 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. $(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. $(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

  1. $V_{1}(G):=\\{v\in V(G)$ such that some maximum matching avoids $v\\}$,

  2. $V_{2}(G):=\\{v\in V(G)$ such that $v$ has a neighbour in $V_{1}(G)$, but $v\notin V_{1}(G)\\}$,

  3. $V_{3}(G):=V(G)\setminus(V_{1}(G)\cup V_{2}(G))$.

Now the following statements hold.333We 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. $(1)$

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

  2. $(2)$

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

  3. $(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. $(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.

1213212312132123$\alpha(v_{i})=\left.\begin{cases}1,&\text{for }i\equiv 3\
(\mathrm{mod}\ 4)\\\ 2,&\text{for }i\equiv 1\ (\mathrm{mod}\ 4)\\\
3,&\text{for }i\equiv 0,2\ (\mathrm{mod}\
4)\end{cases}\right.\mbox{~{}~{}~{}~{}}\alpha(w_{i})=\left.\begin{cases}1,&\text{for
}i\equiv 1,2\ (\mathrm{mod}\ 4)\\\ 2,&\text{for }i\equiv 3,4\ (\mathrm{mod}\
4).\end{cases}\right.$ 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 to444If $\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. $(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. $(2)$

Bipartite graphs, not necessarily complete.

  3. $(3)$

Outerplanar graphs and, more generally, planar graphs.

  4. $(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. $(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. $(2)$

Complete bipartite graphs.

  3. $(3)$

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

  4. $(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 Coalition555For 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.