% Version 4.24 -- October 2026.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,booktabs,array,microtype,enumitem,needspace,tikz}
\usepackage[hidelinks]{hyperref}
\widowpenalty=10000
\makeatletter\def\@cite#1#2{[{#1\if@tempswa ,\nobreakspace #2\fi}]}\makeatother
\clubpenalty=10000
\hypersetup{pdftitle={The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs},pdfauthor={Dave Goel},
  pdfkeywords={graph recolouring, reconfiguration, degenerate graphs, bipartite graphs, Cereceda conjecture}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\diam}{\operatorname{diam}}
\newcommand{\Rk}[1]{\mathcal{R}_{#1}}
\raggedbottom
\emergencystretch=3em

\title{The Cereceda (2007) conjecture holds\\ for bipartite 2-degenerate graphs}
\author{Dave Goel\thanks{\raggedright The Lean~4 proof of this paper's results:\newline
\url{https://github.com/david44hello/paper_cereceda-2007-conjecture-bipartite-2-degenerate/tree/v4.24}}}
\date{\small October 2026}

\begin{document}
\maketitle

\begin{abstract}
For a graph $G$ and a positive integer $k$, the $k$-recolouring graph $\Rk{k}(G)$ has the proper $k$-colourings of $G$ as
vertices, two of them adjacent when they differ at exactly one vertex. A graph is $d$-degenerate if each of its non-empty
subgraphs has a vertex of degree at most $d$. The Cereceda (2007) conjecture states that, for fixed $d$ and $k \ge d+2$,
the diameter of $\Rk{k}(G)$ is $O(n^2)$ for every $d$-degenerate graph $G$ on $n$ vertices. For $d = 2$, the conjecture was known to hold for $k \ge 5$ by a result of
Cereceda; for $k = 4$, the best bound known for all $2$-degenerate graphs is $O(n^3)$, due to Bousquet and Heinrich. We prove that the diameter of $\Rk{4}(G)$ is at most $2n(n+1)$ for every
bipartite $2$-degenerate graph $G$ on $n$ vertices; hence the conjecture holds for these graphs. We also show that the order
$n^2$ cannot be improved for this class, even for graphs of girth $6$. For the upper bound, we fix an ordering of the vertices in which each vertex has at most
two later neighbours. In $n$ stages, we transform any proper $4$-colouring into the
colouring in which every vertex has the least colour not used by its later neighbours, recolouring each vertex at most
twice per stage. Both of our bounds have also been proved in the Lean proof assistant.
\end{abstract}

\section{Introduction}\label{sec:intro}

We prove the Cereceda (2007) conjecture for bipartite $2$-degenerate graphs. The conjecture concerns
\emph{$d$-degenerate} graphs, in which every non-empty subgraph has a vertex of degree at most~$d$. It asserts that, for fixed $d$ and every number of colours $k \ge d+2$,
any proper $k$-colouring of a $d$-degenerate graph on $n$ vertices can be transformed into any other by $O(n^2)$
recolourings of single vertices, with every intermediate colouring proper. Since Cereceda settled
the case $k \ge 5$ \cite[Thm.~5.22]{Cer07}, only the case $k = 4$ is open for $2$-degenerate graphs. Feghali, Johnson and Paulusma \cite{FJP16} call
this case ``a very challenging problem''. We show that
any proper $4$-colouring of a bipartite $2$-degenerate graph on $n$ vertices can be transformed into any other in this way by at most
$2n(n+1)$ recolourings. We also show that the order $n^2$ of
this bound cannot be improved, even for graphs of girth $6$.

All graphs are finite and simple. For a graph $G$ on $n$ vertices and a positive integer $k$, the
\emph{$k$-recolouring graph} $\Rk{k}(G)$ has the proper $k$-colourings of $G$ as vertices, two of them adjacent if
they differ at exactly one vertex, that is, by a \emph{move} recolouring one vertex; we write $\diam \Rk{k}(G)$ for its diameter. The Glauber dynamics, a Markov chain that recolours one vertex at a time, can reach every
$k$-colouring from every other exactly when $\Rk{k}(G)$ is connected \cite{DFFV06, Cer07}. The \emph{degeneracy} of a graph is
the least $d$ for which it is $d$-degenerate. A $d$-degenerate graph $G$ has a proper $(d+1)$-colouring,
and $\Rk{k}(G)$ is connected for every $k \ge d+2$ (Dyer, Flaxman, Frieze and Vigoda \cite{DFFV06}; Cereceda, van den Heuvel and
Johnson \cite{CvdHJ08}; see also \cite[Thm.~2.7]{Cer07}). The graph $\Rk{d+1}(G)$ can be disconnected (for
example, for $G = K_{d+1}$), and for $d \ge 3$ it can have a component of diameter $2^{\Omega(\sqrt{n})}$
\cite[Thm.~1.4]{BC09}, \cite[Thm.~5.2 and p.~109]{Cer07}.
The Cereceda (2007) conjecture is the following.

\begin{conjecture}[Cereceda {\cite[Conj.~5.21]{Cer07}}]\label{conj:cereceda}
For all integers $d \ge 1$ and $k \ge d+2$, there is a constant $C$ such that $\diam \Rk{k}(G) \le C n^2$ for every
$d$-degenerate graph $G$ on $n$ vertices.
\end{conjecture}
Cereceda states it with $d$ equal to the degeneracy of $G$. The two forms are equivalent for graphs with at least one edge,
since a $d$-degenerate graph with an edge has degeneracy between $1$ and $d$, and we can take for $C$ the largest
of the constants that Cereceda's form gives for these degeneracies and the same $k$.

\begin{theorem}\label{thm:bip}
For every bipartite $2$-degenerate graph $G$ on $n$ vertices, $\diam \Rk{4}(G) \le 2n(n+1)$.
\end{theorem}

\begin{proposition}\label{prop:lb}
The order $n^2$ in Theorem~\ref{thm:bip} cannot be improved. For every $n \ge 7$ there is a planar bipartite graph of
degeneracy $2$ on $n$ vertices whose $4$-recolouring graph has diameter at least $(n-7)^2/8$, and for every $n \ge 33$ there
is a bipartite graph of degeneracy $2$ and girth $6$ on $n$ vertices whose $4$-recolouring graph has diameter at least
$(n-33)^2/128$.
\end{proposition}

\begin{table}[ht]
\centering
\small
\caption{Our results and the best previous results for $d = 2$ and four colours.}\label{tab:compare}
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{0.47\textwidth}@{\hspace{0.03\textwidth}}>{\raggedright\arraybackslash}p{0.50\textwidth}@{}}
\toprule
New result & Best result before this paper\\
\midrule
$\diam \Rk{4}(G) \le 2n(n+1)$ for every bipartite $2$-degenerate graph $G$ on $n$ vertices
(Theorem~\ref{thm:bip}).
& $O(n^3)$ for every $2$-degenerate graph \cite[Thm.~1]{BH22}. Quadratic or better, to our knowledge, only for the classes
(i)--(v) below, which do not cover all bipartite $2$-degenerate graphs.\\
\addlinespace
Order $n^2$ is best possible for bipartite $2$-degenerate graphs, even at girth $6$ (Proposition~\ref{prop:lb}).
& Order $n^2$ on fans, which are $2$-degenerate but not bipartite \mbox{\cite[Thm.~12]{BJLPP14}}.\\
\bottomrule
\end{tabular}
\end{table}

Cereceda proved that $\diam \Rk{k}(G) = O(n^2)$ for every $d$-degenerate graph $G$ on $n$ vertices and every
$k \ge 2d+1$ \cite{Cer07}, which covers $d = 1$. With $k \ge 2d+2$ colours the diameter is linear, by a theorem of Bousquet and Perarnau
\cite[Thm.~1]{BP16}. The order $n^2$ is best possible for every $d$ when $k = d+2$. Take a path and join every vertex of a clique on $d - 1$
vertices to every vertex of the path (for $d = 2$, a \emph{fan}). This graph is $d$-degenerate, and its $(d+2)$-recolouring
graph has diameter of order $n^2$ \cite[Thms.~11 and~12]{BJLPP14}. For $d+2$ colours and $d \ge 2$, the first polynomial bound, $\diam \Rk{d+2}(G) = O(n^{d+1})$ for every
$d$-degenerate graph $G$ on $n$ vertices, is due to Bousquet and Heinrich \cite[Thm.~1]{BH22} (see Table~\ref{tab:compare} for $d = 2$). The same theorem gives
the bound
$O(n^2)$ for $k \ge \tfrac32(d+1)$. For planar bipartite graphs, which are $3$-degenerate by Euler's formula, they also proved that
$\diam \Rk{5}(G) = O(n^2)$ \cite[Thm.~2]{BH22}. They describe this as proving the conjecture for planar bipartite graphs. Cranston
and Mahmoud noted that this result settles the case of degeneracy $3$ \cite{CM24}.

Since $d$ in Conjecture~\ref{conj:cereceda} may be any upper bound on the degeneracy, the conjecture for planar bipartite
graphs also asks for four colours when $d = 2$. For these graphs, Theorems~1 and~2 of \cite{BH22} give
$\diam \Rk{k}(G) = O(n^2)$ for every $k \ge 5$, and Cereceda's theorem for $k \ge 2d+1$.
With Theorem~\ref{thm:bip}, the conjecture holds for all planar bipartite graphs. To our knowledge, the case $d = 2$, $k = 4$
was the only one still open.

\paragraph{Outline of the proofs.}
Let $G$ be a bipartite $2$-degenerate graph. Fix an ordering $v_1, \dots, v_n$ of its vertices in which every vertex has at
most two later neighbours (a degeneracy ordering, see Section~\ref{sec:setting}). We use the colours $0 < 1 < 2 < 3$. A vertex
is \emph{on} $y$ if it has the colour $y$. It is \emph{greedy} if it has the least colour that none of its later neighbours has.
In the \emph{sweep}, we start from any colouring and make $v_1, v_2, \dots, v_n$ greedy in turn, one per stage. Making $v_t$ greedy may
force us to move earlier vertices too, since an earlier neighbour of $v_t$ may be on the colour that $v_t$ must take. But only the
\emph{cone} of $v_t$ is involved, formed by $v_t$ and the earlier vertices from which $v_t$ can be reached by repeatedly passing
to a later neighbour. Since no vertex outside the cone has a later neighbour in it, recolouring the cone cannot make a vertex outside it
non-greedy. At the start of stage $t$, every vertex of the cone except possibly $v_t$ is greedy. We must reach the
\emph{target colouring} of the cone, in which every vertex is greedy.

If $v_t$ must take a colour other than $0$, the current and the target colouring put the same vertices of the cone on $0$, and we
leave these vertices alone. Every other vertex of the cone has a later neighbour on $0$ and so at most one later neighbour not on $0$.
The vertices not on $0$ therefore form a forest. The two colourings differ only on the tree of this forest that contains $v_t$,
where both use only the colours $1$, $2$ and $3$. On a tree, a $3$-colouring $c$ lifts to a \emph{height function}, an integer
function $h$ with $h \equiv c \pmod 3$ that changes by $\pm 1$ along every edge. A move changes $h$ by $\pm 2$ at the moved vertex
only. Two colourings whose height functions $h$ and $h'$ differ by an even number at every vertex are
joined by moves in which each vertex $v$ moves exactly $|h'(v) - h(v)|/2$ times. Away from $v_t$, both colourings alternate between
$1$ and $2$ along the tree, so each height function $h$ stays between $h(v_t) - 1$ and $h(v_t) + 2$. We can thus choose the
two height functions to differ by $0$, $\pm 2$ or $\pm 4$ at every vertex, and then each vertex moves at most twice.

If $v_t$ must move to the colour $0$, the vertices on $0$ change. Here we use that the cone, like $G$, is
bipartite. We construct a colouring $\mu$ of the cone that is at least as large as both the current and the target colouring at
every vertex. If we raise the vertices to their colours in $\mu$ in decreasing order of $\mu$, and then lower
them to their target colours in increasing order of $\mu$, every intermediate colouring is proper and each vertex moves at most
twice. We choose $\mu$ greedily, from $v_t$ down the ordering: each vertex takes the least colour that is at least its
current and its target colour and differs from the colours of its later neighbours, read in $\mu$ inside the cone and in the
current colouring outside it. Counting colours, we see that this rule can get stuck only at a vertex that is on $2$ in the current
or the target colouring and has two later neighbours in the cone, if these take both $2$ and $3$ in $\mu$.

Bipartiteness prevents this. We show that the vertices that leave $0$ or go from $2$ to $1$ during the stage lie on
one side of the bipartition, and those that join $0$ or go from $1$ to $2$ lie on the other. Suppose
that a vertex where the rule could get stuck is on $2$ in the current colouring (the case of the target colouring is symmetric). Its two later neighbours are on $0$ and on $1$, and they cannot
both change colour. Otherwise the one on $0$ would leave $0$ and the one on $1$ would join $0$ or go to $2$ (a greedy vertex is never on $3$).
This would put them on different sides, although both are adjacent to the vertex. So one of them keeps its colour, $0$ or $1$. It keeps this colour in
$\mu$ too, leaving $2$ or $3$ for the vertex. Without bipartiteness, such a $\mu$ need not exist (Remark~\ref{rem:triangle}).

In both cases we move each vertex of the cone at most twice in a stage. As the cone of $v_t$ has at most $t$ vertices, the sweep
makes at most $2(1 + 2 + \dots + n) = n(n+1)$ moves. It ends at the colouring in which every vertex is greedy.
This colouring is unique, since its colours are forced in the order $v_n, \dots, v_1$. Joining two colourings through it, we
obtain the bound $2n(n+1)$.

Our sweep follows the scheme of Bonamy and Bousquet for graphs of bounded treewidth \cite{BB18}, in which the
vertices are settled one at a time, every earlier vertex moves at most twice per stage, and any two colourings are joined through
canonical colourings, unique up to a permutation of the colours. Settling the vertices along a degeneracy ordering goes back to
Cereceda's proof of the bound for $k \ge 2d+1$ \cite{Cer07}, which settles them in the opposite order and never recolours a
settled vertex. In the proof of \cite[Lemma~9]{BH22}, Bousquet and Heinrich go in our order, $v_1, v_2, \dots$, a fixed number
of vertices at a time, and recolour only vertices already treated. From them we also take the restriction of a stage to an
induced subgraph, here the cone, in which each vertex gets as its list the colours not used by its neighbours
outside the subgraph. Following them, we call a colour \emph{full} if every vertex whose list contains it has it or has a later
neighbour with it; removing the vertices of a full colour lowers the degeneracy by one, as they observe. When $v_t$ must take a colour
other than $0$, the colour $0$ is full in both colourings. The vertices not on $0$ then form a forest. For $d = 2$, Bousquet and Heinrich bound the moves for each new vertex
by order $n^2$, which gives their $O(n^3)$. Our new ingredient is the colouring $\mu$ of Definition~\ref{def:mu}, with
which a stage inside a bipartite cone needs at most two moves per vertex.

The lower bounds adapt two proofs of \cite{BJLPP14}, one for $3$\nobreakdash-colourings of a path, which builds on
\cite{CvdHJ11}, and one for $4$\nobreakdash-colourings of fans; we measure distances between colourings with height functions. We
replace the apex of the fan, its vertex adjacent to all path vertices, by two additional vertices $a$ and $b$, adjacent to
the path vertices of odd and of even index respectively. For girth $6$ we use four, $a_0, \dots, a_3$, where $a_j$ is adjacent
to the path vertices whose index is congruent to $j$ modulo $4$. In both families, unlike the apex, these vertices keep the
graph bipartite. In the two colourings that we compare they have the colour $3$, and while they keep it the path
cannot use it. The other three colours increase cyclically along the path in one of these colourings and decrease in the
other, so if the path has $\ell$ vertices, its height function changes from end to end by $\ell - 1$ in one and by
$-(\ell - 1)$ in the other. An additional vertex can leave the colour $3$ only if its path neighbours miss one of the
other three colours. This limits the end-to-end change to at most $4$ in absolute value in the planar
family, and to about $3\ell/4$ in the family of girth $6$. A height function with this bounded end-to-end change differs from
those of the two colourings by order $\ell^2$, summed over the vertices of the path, while a move changes a height function at
only one vertex, by $\pm 2$. So order $\ell^2$ moves precede the first move of an additional vertex, and as many follow the last one. If the additional vertices never leave the colour $3$, the moves change the height function from that of one colouring
to that of the other, which also takes order $\ell^2$ moves.


\needspace{5\baselineskip}
\paragraph{Comparison with known classes.}
Among bipartite $2$-degenerate graphs, quadratic or better bounds for four colours were known, to our knowledge, only for
the following five classes, with the bounds shown:
\begin{enumerate}[label=(\roman*),leftmargin=2.4em,itemsep=0pt,topsep=2pt]
\item graphs of treewidth at most $2$, with $2n(n+1)$ \cite[Thm.~2]{BB18};
\item graphs of maximum degree at most $3$, with $O(n^2)$ \cite[Thm.~5]{FJP16}, and $O(n)$ for connected graphs of maximum
degree $3$ \cite[Thm.~1.3]{BFHR25};
\item $3$-colour-dense graphs, with $2n^2$ \cite[Thm.~2]{BJLPP14};
\item graphs of Grundy number at most $3$, with $4\chi(G)\,n$ \cite[Thm.~1]{BB18}, where $\chi(G)$ is the chromatic number;
for bipartite $G$ this is at most $8n$;
\item graphs of maximum average degree (the largest average degree of a subgraph) at most $3-\varepsilon$ for a fixed $\varepsilon > 0$, with $O(n\log^2 n)$
\cite[Thm.~1]{Feg21}.
\end{enumerate}

In (ii), Theorem~1.3 of \cite{BFHR25} assumes that, in each of the two colourings, some vertex can be recoloured.
This holds for every non-empty $2$-degenerate graph, since such a graph has a vertex of degree at most $2$, and with four colours such a vertex can
always be recoloured.



The \emph{Grundy number} in (iv) is the largest number of colours that a \emph{first-fit colouring} can use. A first-fit
colouring takes the vertices one at a time, in some order, and gives each the least positive integer not used by an earlier
neighbour. Class (iv) contains many bipartite $2$-degenerate graphs, for example every graph obtained from a graph by
subdividing each of its edges once. In a first-fit colouring of such a graph, a subdivision vertex that is coloured before an
original neighbour $v$ had at most one coloured neighbour and so received the colour $1$ or $2$. Then $v$ receives a colour at
most $3$, and so does every subdivision vertex, as it has only two neighbours.

The other classes with quadratic bounds for four colours that we know of contain no bipartite graph outside (i)--(v). For
example, \cite[Thm.~4]{BB18} gives a quadratic bound with $k \ge \chi(G) + 1$ colours for every \emph{distance-hereditary}
graph $G$ (a graph in which any two vertices of a connected induced subgraph are at the same distance in the subgraph as
in the whole graph), including four colours when $\chi(G) \le 3$. The $3$-colourable OAT graphs of Biedl, Lubiw and Merkel have a quadratic bound for four colours \cite[Thm.~3.3]{BLM21}. By Remark~\ref{rem:dhoat}, the bipartite graphs in both
classes lie in (iii).

The union of the classes (i)--(v) does not contain all bipartite $2$-degenerate graphs. For $\ell \ge 15$, the
bipartite graph $J_\ell$ of girth $6$ in Section~\ref{sec:girth6}, a path on $\ell$ vertices with $a_0, \dots, a_3$, lies in
none of them
(Remark~\ref{rem:Jl}). For $\ell \ge 29$ these graphs give the lower bound for girth $6$ in Proposition~\ref{prop:lb}, so on them the
bound of Theorem~\ref{thm:bip} has the best possible order $n^2$.

An expanded version of this paper, with many other results, is posted on Zenodo \cite{G}. The proofs in this paper do not
depend on \cite{G}.

\section{Degeneracy orderings and the reduction to cones}\label{sec:setting}

Throughout Sections~\ref{sec:setting} and~\ref{sec:bip}, $G$ is a $2$-degenerate graph on $n$ vertices. A
\emph{colouring} of $G$ is a proper colouring with the colours $0 < 1 < 2 < 3$. Recall that a vertex is on $y$ if it has the
colour $y$. A \emph{degeneracy ordering} of $G$ is an ordering $v_1, \dots, v_n$ of its vertices in which every
vertex $v$ has at most two later neighbours. We call them the \emph{out-neighbours} of $v$ and write $N^+_G(v)$ for their set. Since $G$ is $2$-degenerate, we obtain such an ordering by repeatedly deleting a vertex of
degree at most $2$ and listing the vertices in the order of deletion. We orient each edge from its earlier end to its later end and call the oriented edges \emph{arcs}.
The \emph{greedy colour} of a vertex $v$ in a colouring $c$ of $G$ is the least colour that no out-neighbour of $v$ has. We call
$v$ \emph{greedy} in $c$ if $c(v)$ is its greedy colour. In stage $t = 1, \dots, n$ of the \emph{sweep}, we make $v_t$ greedy and keep
$v_1, \dots, v_{t-1}$ greedy.

\begin{definition}
For $1 \le t \le n$, the \emph{cone} $C_t$ is the set of vertices from which $v_t$ can be reached along a directed path of
arcs, including $v_t$ itself.
\end{definition}
Since arcs point to later vertices, $C_t \subseteq \{v_1, \dots, v_t\}$. Thus $\sum_t |C_t| \le n(n+1)/2$.

At stage $t$ of the sweep, we recolour only the vertices of $C_t$. This is a
list-recolouring problem on $C_t$: a vertex of $C_t$ may not use the colours of its out-neighbours outside $C_t$, and $v_t$ may use
only its current colour $x$ and its greedy colour $g$ (we shall move it once, from $x$ to $g$). A vertex of $C_t$ has no other
neighbours outside $C_t$, since a vertex with an arc into $C_t$ lies in $C_t$. As every vertex has at most two out-neighbours and there are four colours, every vertex
of $C_t$ other than $v_t$ keeps at least two more colours than it has out-neighbours inside $C_t$. This is the condition on the lists in
the next definition, where we state the problem without reference to $G$ and list the vertices in reverse order, so
that out-neighbours come first.

\begin{definition}\label{def:instance}
An \emph{instance} consists of a finite set of vertices with a linear order, the \emph{instance order}, together with
out-neighbour sets and lists of colours, given as follows. Its first vertex is the \emph{sink} $s$. Every vertex $v$ has a set $N^+(v)$ of at most two \emph{out-neighbours}, all of them before $v$ in the
instance order (the sink has none). The \emph{edges} of the instance are the pairs $\{v,u\}$ with $u \in N^+(v)$, and the two ends of an edge are \emph{neighbours}. The instance is \emph{bipartite} if these edges form a
bipartite graph. It is \emph{single-sink} if $s$ is its only vertex without out-neighbours.
Every vertex $v$ has a list
$L(v) \subseteq \{0,1,2,3\}$ with $|L(v)| \ge |N^+(v)| + 2$ (a $1$-feasible list assignment of \cite{BH22}), and the sink has a list $\{g, x\}$ with~$0 \le g < x \le 3$.

A \emph{colouring} of an instance gives
every vertex $v$ a colour of $L(v)$, and it is \emph{proper} if the two ends of every edge have different colours. Two
colourings $\alpha$ and $\beta$ are defined \emph{greedily}: $\alpha(s) = x$, $\beta(s) = g$, and every other vertex $v$, in
instance order, takes its \emph{greedy} colour in the instance, the least colour of its list that none of its out-neighbours has. This
colour exists since $|L(v)| > |N^+(v)|$. The colourings $\alpha$ and $\beta$ depend only on the out-neighbours and the lists,
not on the instance order, and both are proper, since every vertex avoids the colours of its out-neighbours. In an instance, a
\emph{move} gives one vertex another colour of its list, one that none of its neighbours has. A \emph{sequence from $\alpha$ to $\beta$} consists of
finitely many moves that, applied in order, transform $\alpha$ into $\beta$, and its \emph{length} is the number of its moves.
\end{definition}

For $1 \le t \le n$, the \emph{instance on $C_t$} has the vertices of $C_t$ in decreasing order of index
as its instance order and $v_t$ as its sink. The out-neighbours of a vertex $v \in C_t$ in the instance are the vertices of
$N^+_G(v) \cap C_t$. Thus every vertex comes after its out-neighbours, $v_t$ has none, and every other vertex of $C_t$ has one in $C_t$, the next
vertex on a directed path of arcs to $v_t$. So the instance on $C_t$ is single-sink. We choose its lists in the proof of Lemma~\ref{lem:sweep}, so that $\alpha$ is the
colouring of $C_t$ at the start of stage $t$ and $\beta$ is the target colouring, in which every vertex of $C_t$ is greedy.
Only the case $g = 0$,
treated in Section~\ref{sec:bip}, needs bipartiteness and the single-sink property.

\begin{lemma}\label{lem:caseA}
Let an instance have $m$ vertices, and let its sink have the list $\{g, x\}$ with $0 < g < x$. Then there is a sequence from
$\alpha$ to $\beta$ of length at most $2m$, in which the sink moves exactly once and every other vertex at most twice.
\end{lemma}
To prove it, we use height functions of $3$-colourings of trees
\cite{GMP04}, \cite[\mbox{Section~3.1}]{Cer07}.
Let $T$ be a tree and $c$ a proper colouring of $T$ with colours in $\{1,2,3\}$. A \emph{height function}
of $c$ is a function $h \colon V(T) \to \mathbb{Z}$ with $h(v) \equiv c(v) \pmod 3$ for all $v$ and $|h(u) - h(v)| = 1$ for
every edge $\{u,v\}$. Since $T$ is a tree and the colours of adjacent vertices differ by $\pm 1$ modulo $3$, such a function exists (fix $h$ at one
vertex and extend it along the edges). It is unique up to adding a constant in $3\mathbb{Z}$.
As in \cite{CvdHJ11}, we compare the height functions of the current and the target colouring.
A move changes the current height function by $\pm 2$ at the moved vertex only. (In a $3$-colouring of a tree, a vertex can be recoloured
only when all its neighbours have the same colour, and then its height changes by $\pm 2$.) In
Lemma~\ref{lem:T} we adapt \cite[Lemma~3.2]{Cer07} to trees with a restricted set of colours at one vertex and
count the moves exactly. Cereceda attributes that lemma to Goldberg, Martin and Paterson \cite{GMP04}, and our proof
follows Cereceda's.

\begin{lemma}\label{lem:T}
Let $T$ be a tree and $r$ a vertex of $T$; the allowed colours are $1,2,3$ at every vertex other than $r$, and those of a set
$P \subseteq \{1,2,3\}$ at $r$. Let $c, c'$ be proper colourings of $T$ with allowed colours, $h$ a height function of $c$,
and $E \colon V(T) \to 2\mathbb{Z}$ a function such that $h + E$ is a height function of $c'$ and $|E(r)| \le 2$ if
$|P| \le 2$. Then $c$ can be transformed into $c'$ by exactly $\frac12 \sum_v |E(v)|$ moves through proper colourings with
allowed colours, in which every vertex $v$ moves exactly $|E(v)|/2$ times.
\end{lemma}
The condition on $E(r)$ makes $r$, which may have fewer than three allowed colours, move at most once, and then directly to
$c'(r)$.
\begin{proof}
We use induction on $\sum_v |E(v)|$. If $E = 0$, then $c' = c$. Suppose that $E(v) > 0$ for some $v$. We choose such a $v$ with $h(v)$ least. If a neighbour
$u$ had $h(u) = h(v) - 1$, then, since $h + E$ is a height function and $E(v) \ge 2$, $(h+E)(u) \ge (h+E)(v) - 1 \ge h(v) + 1 = h(u) + 2$, so $E(u) \ge 2$ and $h(u) < h(v)$, contradicting the
choice of $v$. Thus $h(u) = h(v) + 1$ for every neighbour $u$ of $v$. In other words, $v$ is a local minimum of $h$. All its neighbours
have the colour congruent to $h(v)+1$ modulo $3$. We recolour $v$
with the colour $y \in \{1,2,3\}$ such that $y \equiv h(v) + 2 \pmod 3$. The colouring stays proper. The colour $y$ is allowed at $v$ if $v \ne r$ or
$|P| = 3$. If $v = r$ and $|P| \le 2$, then $E(r) = 2$. Hence $c'(r) \equiv h(r) + 2 \pmod 3$, that is, $y = c'(r)$, an allowed colour. The new
colouring has the height function $h + 2\mathbf{1}_v$, where $\mathbf{1}_v$ is the indicator function of $\{v\}$. Since $E(v) \ge 2$, the
function $E - 2\mathbf{1}_v$ has absolute value $|E(v)| - 2$ at $v$. Thus $\sum_u |E(u)|$ drops by $2$. The function $E - 2\mathbf{1}_v$ still satisfies the
hypotheses (if $v = r$ and $|P| \le 2$, its value at $r$ is $0$). By induction, every vertex $u$ moves exactly $|E(u)|/2$ times in all. If $E \ne 0$ but no $E(v) > 0$, we argue symmetrically with
$E(v) < 0$ and $h(v)$ largest.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:caseA}]
We show that $\alpha$ and $\beta$ put the same vertices on $0$, that the other vertices induce a forest, and that $\alpha$ and
$\beta$ differ only on the tree $T$ of this forest that contains $s$. Lemma~\ref{lem:T} applies to $T$, where both colourings use only $1$, $2$
and $3$. Since $g > 0$, the sink is not on $0$ in $\alpha$ or in $\beta$. A vertex $v \ne s$ is on $0$ in $\alpha$ if and only if
$0 \in L(v)$ and no out-neighbour of $v$ is on $0$ in $\alpha$. The same holds for $\beta$. By induction along the instance
order, $\alpha^{-1}(0) = \beta^{-1}(0)$, and we call this set $U$. This rule also shows that the colour $0$ is full in $\alpha$ and in $\beta$, that is, every vertex whose list
contains $0$ is on $0$ or has an out-neighbour on $0$. Let $F$ be the set of the other vertices.

\emph{Claim 1. Every $v \in F$ has at most one out-neighbour in $F$.} If $0 \in L(v)$, then, since $v$ is not on~$0$ in
$\alpha$, some out-neighbour of $v$ is on $0$ and lies in $U$. Otherwise $|L(v)| \le 3$, and since
$|L(v)| \ge |N^+(v)| + 2$, the vertex $v$ has at most one out-neighbour.
Thus $F$ induces a forest in which each vertex has at most one \emph{parent} (an out-neighbour in $F$), since on a cycle in $F$
the vertex that comes last in the instance order would have both its neighbours on the cycle as out-neighbours in $F$.
All neighbours of a vertex of $F$ other than its parent and its children (the vertices of $F$ whose parent it is) lie in $U$. In particular, if a vertex outside a component of the forest induced by $F$ is
adjacent to this component, then it lies in $U$.

\emph{Claim 2. Every vertex $v$ of $F$ with a parent has $\{1,2,3\} \subseteq L(v)$.} If $0 \in L(v)$, then $v$ has an
out-neighbour on $0$ and a parent, so $|L(v)| = 4$; otherwise $L(v) = \{1,2,3\}$.

A vertex $w \ne s$ of $F$ without a parent has all its out-neighbours on $0$, so $\alpha(w) = \beta(w) = \min (L(w) \setminus \{0\})$. A vertex
of $F$ with a parent $p$ is not on $0$, by Claim~2 its list contains $1$, $2$ and $3$, and its other out-neighbour, if any, is on $0$.
So in $\alpha$ and in $\beta$ it takes the least colour of $\{1,2,3\}$ other than the colour of $p$. By induction, we get
$\alpha = \beta$ outside the component $T$ of the forest induced by $F$ that contains $s$ (the vertices of $U$ are on $0$ in
both colourings, and every other vertex outside $T$ has its parent, if any, outside $T$). Moreover, in each colouring $c \in \{\alpha, \beta\}$, every child
of a vertex on $1$ is on $2$, and every child of a vertex on $2$ or $3$ is on $1$.

As a tree, $T$ has $|T| - 1$ edges, each joining a vertex to its parent. Since each vertex has at most one parent,
the sink $s$ is the only vertex of $T$ without one. Every other vertex of $T$ is reached
from $s$ by passing repeatedly from a vertex to one of its children. Along such a path the colours are $1, 2, 1, 2, \dots$
if $c(s) = 1$, they are $2, 1, 2, 1, \dots$ if $c(s) = 2$, and they are $3, 1, 2, 1, 2, \dots$ if $c(s) = 3$. For a height function $h$ of $c|_T$ and every $v \in T \setminus \{s\}$, we have
\begin{equation}\label{eq:heights} h(v) - h(s) \in \begin{cases} \{0,1\} & \text{if } c(s) = 1,\\ \{-1,0\} & \text{if } c(s) = 2,\\ \{1,2\} & \text{if } c(s) = 3. \end{cases} \end{equation}

We choose height functions $h_\alpha$ of $\alpha|_T$ and $h_\beta$ of $\beta|_T$. Since $\alpha(s) \ne \beta(s)$ are colours in $\{1,2,3\}$,
the difference $h_\beta(s) - h_\alpha(s)$ is congruent to $2$ or to $-2$ modulo $3$. Shifting $h_\beta$ by a multiple of $3$, we may assume that
$E = h_\beta - h_\alpha$ has $E(s) \in \{-2, 2\}$. For
$v \in T \setminus \{s\}$, write $E(v) - E(s) = (h_\beta(v) - h_\beta(s)) - (h_\alpha(v) - h_\alpha(s))$. By~\eqref{eq:heights}, both
brackets lie in $[-1, 2]$. Both also have the parity of $\mathrm{dist}_T(v,s)$, since a height function changes by $\pm 1$ along every
edge. Their difference is even and lies in $[-3, 3]$, i.e.\ in $\{-2, 0, 2\}$. Since $E(s) = \pm 2$, the function $E$ is
even with $|E(v)| \le 4$ for every $v \in T$.

Since $|E(s)| = 2$, Lemma~\ref{lem:T} applies to $T$, with $r = s$ and $P = L(s) = \{g, x\}$. Every other vertex
of $T$ has a parent in $T$. By Claim~2, its list contains $1$, $2$ and $3$, the only colours the moves of Lemma~\ref{lem:T} use.
Every vertex outside $T$ that is adjacent to $T$ lies in $U$ and is on $0$. So these moves are moves of the instance, $U$ stays
on $0$, and no vertex outside $T$ moves. They turn $\alpha$ into $\beta$ in $\frac12 \sum_{v \in T} |E(v)| \le 2|T| \le 2m$ moves, in which
$s$ moves once and every other vertex at most twice, since $|E(s)| = 2$ and $|E(v)| \le 4$.
\end{proof}

The next lemma turns a bound for the case $g = 0$ into a bound on $\diam \Rk{4}(G)$. We state it for a class $\mathcal{K}$ of
instances, as we also use it for the first open problem in Section~\ref{sec:open}.

\needspace{7\baselineskip}
\begin{lemma}\label{lem:sweep}
Let $\mathcal{K}$ be a class of instances that is closed under changing the lists (to any other lists
allowed in an instance), and let $\lambda \ge 2$ be such that every
instance in $\mathcal{K}$ with $g = 0$ has a sequence from $\alpha$ to $\beta$ of length at most $\lambda m$, where $m$ is
its number of vertices. Let $G$ have a degeneracy ordering such that, for every $t$, the instance on $C_t$ lies in $\mathcal{K}$
for some choice of lists (and so, by the closure property, for every choice). Then
\[ \diam \Rk{4}(G) \le 2\lambda \sum_t |C_t| \le \lambda n(n+1). \]
\end{lemma}
\begin{proof}
Giving $v_n, v_{n-1}, \dots, v_1$ in turn their greedy colours, we
obtain the only colouring $\gamma$ in which all vertices are greedy. This is the first-fit colouring in the order
$v_n, \dots, v_1$ with the colours $0 < 1 < 2 < 3$. Bousquet and Heinrich \cite[Section~2]{BH22} note that it has a full colour (here the colour $0$). We show that $\gamma$ can be reached from any colouring in at most $\lambda \sum_t |C_t|$ moves. We can then join any two colourings
through $\gamma$ by at most $2\lambda \sum_t |C_t|$ moves.

We prove that after stage $t$ of the sweep the vertices $v_1, \dots, v_t$ are greedy. At stage $t$, let $c$ be
the current colouring, $x = c(v_t)$, and $g$ the greedy colour of $v_t$. If $x = g$, stage $t$ makes
no move. Otherwise we take the instance on $C_t$ with the lists $L(v_t) = \{g, x\}$ and, for every other $v \in C_t$,
$L(v) = \{0,1,2,3\} \setminus c(N^+_G(v) \setminus C_t)$. Here $g < x$, since no out-neighbour of $v_t$ has the
colour $x$ ($c$ is proper) and $g$ is the least colour with this property. For every other $v \in C_t$,
$|L(v)| \ge 4 - |N^+_G(v) \setminus C_t| \ge |N^+_G(v) \cap C_t| + 2$, since $|N^+_G(v)| \le 2$. So these lists are allowed in an instance.

Recall that every neighbour of a vertex $v \in C_t$ outside $C_t$ is an
out-neighbour of $v$. The edges of $G$ inside
$C_t$ are exactly the edges of the instance, and the neighbours outside $C_t$ do not move and their colours are not in the lists.
Every sequence in the instance is thus also a sequence of moves in $G$.

Both $c|_{C_t}$ and $\alpha$ give $v_t$ the colour $x$, the other vertices of $C_t$ are greedy before the stage, and the greedy
colour of such a vertex in $G$ is the least colour of its list that no out-neighbour inside $C_t$ has. By induction along the
instance order, $c|_{C_t} = \alpha$. Likewise, every vertex of $C_t$ is greedy in the colouring that agrees with $\beta$ on $C_t$
and with $c$ elsewhere. There $v_t$ has the colour $g$, every other vertex of $C_t$ has its greedy colour in the instance, and its
out-neighbours outside $C_t$ keep their colours. A vertex $v_j$ with $j < t$ that lies outside $C_t$ has no
out-neighbour in $C_t$ and stays greedy.

If $g = 0$, the condition on $\mathcal{K}$ gives at most $\lambda|C_t|$ moves. If $g \ne 0$, then
$0 < g < x$ and Lemma~\ref{lem:caseA} gives at most $2|C_t| \le \lambda|C_t|$ moves. After stage $n$ every vertex is greedy, i.e.\ the colouring is $\gamma$. Summing over $t$ gives the bound.
\end{proof}


\section{Proof of Theorem~\ref{thm:bip}}\label{sec:bip}
By Lemma~\ref{lem:sweep}, Theorem~\ref{thm:bip} follows from the next theorem, a bound on the length of a sequence from $\alpha$ to $\beta$ in
bipartite single-sink instances; we make the deduction at the end of this section.

\begin{theorem}\label{thm:BIPinst}
Let a bipartite single-sink instance have $m$ vertices. Then there is a sequence from $\alpha$ to $\beta$ in
which the sink moves exactly once and every other vertex at most twice; in particular, its length is at most $2m - 1$.
\end{theorem}

Throughout this section, instances are single-sink. Every vertex other than the sink then has one or two
out-neighbours. A vertex with two of them has the list $\{0,1,2,3\}$, since $|L(v)| \ge |N^+(v)| + 2$. If the sink has
the list $\{g, x\}$ with $g \ne 0$, Lemma~\ref{lem:caseA} gives a sequence as in Theorem~\ref{thm:BIPinst}. From now on,
$g = 0$. We call a colour \emph{free} at a vertex $v$ in a colouring if no out-neighbour of $v$ has it. Thus $\alpha(v)$ and $\beta(v)$, for $v \ne s$,
are the least free colours of $L(v)$ in $\alpha$ and in $\beta$.

\begin{lemma}\label{lem:s1}
For every vertex $v \ne s$, both $\alpha(v)$ and $\beta(v)$ lie in $\{0,1,2\}$.
\end{lemma}
\begin{proof}
As $|L(v)| \ge |N^+(v)| + 2$, at least $|N^+(v)| + 1$ colours of $L(v)$ lie in $\{0,1,2\}$, and the $|N^+(v)|$
out-neighbours of $v$ cannot use all of them. Hence some colour of $L(v) \cap \{0,1,2\}$ is free in $\alpha$ and in $\beta$.
\end{proof}

We call the pair $(\alpha(v), \beta(v))$ the \emph{pattern} of $v$. Since $g = 0$, the pattern of the sink is $(x, 0)$. A vertex $v$ is
\emph{fixed} if $\alpha(v) = \beta(v)$. It is then \emph{fixed on} the colour $\alpha(v)$. A vertex with a pattern $(0,y)$,
$y \ne 0$, is a \emph{leaver} (it leaves the colour $0$), and one with a pattern $(y,0)$, $y \ne 0$, is a \emph{joiner}
(it joins the colour $0$); the sink is a joiner. We shall see that, in a bipartite
instance, leavers and joiners lie on opposite sides.

\begin{lemma}\label{lem:s3}
In an instance with $g = 0$, every leaver has an out-neighbour that is a joiner, and every joiner other than $s$ has an
out-neighbour that is a leaver.
\end{lemma}
\begin{proof}
A leaver $v$ has $0 \in L(v)$ and is not on $0$ in $\beta$. Then some out-neighbour $u$ has $\beta(u) = 0$, and $\alpha(u) \ne 0$
because $\alpha(v) = 0$. In the same way, a joiner $v \ne s$ has an out-neighbour $u$ with $\alpha(u) = 0$, and $\beta(u) \ne 0$
because $\beta(v) = 0$.
\end{proof}

\begin{lemma}\label{lem:um}
Let $\mu$ be a proper colouring of an instance with $\mu(v) \in L(v)$, $\mu(v) \ge \alpha(v)$ and $\mu(v) \ge \beta(v)$ for every
$v$, and $\mu(s) = x$. Then the following is a sequence from $\alpha$ to $\beta$ in which every vertex moves at most twice and
the sink exactly once: first recolour every vertex $v$ from $\alpha(v)$ to $\mu(v)$, in decreasing order of $\mu$, and then
every vertex $v$ from $\mu(v)$ to $\beta(v)$, in increasing order of $\mu$ (ties in any order; no move when the two colours
agree).
\end{lemma}
\begin{proof}
It suffices to check, for each edge $\{v,w\}$, the moves of $v$ and of $w$. Since $\mu$ is proper, $\mu(v) \ne \mu(w)$. In particular, vertices with the same value of $\mu$ are not
adjacent, so their order does not matter. Suppose that $\mu(w) > \mu(v)$. In the first part $w$ moves first, while $v$ is on
$\alpha(v) \le \mu(v) < \mu(w)$. When $v$ moves, $w$ is on $\mu(w) \ne \mu(v)$. In the second part $v$ moves first, to $\beta(v)$,
while $w$ is on $\mu(w) > \mu(v) \ge \beta(v)$. When $w$ moves to $\beta(w)$, $v$ is on $\beta(v) \ne \beta(w)$. All colours used
lie in the lists. The sink starts on $x = \mu(s)$ and moves only in the second part.
\end{proof}

For example, let the sink $s$ have the list $\{0,1\}$ and $x = 1$, and let one more vertex $u$, with $N^+(u) = \{s\}$, have the
list $\{0,1,2,3\}$. Then $\alpha(u) = 0$ and $\beta(u) = 1$. We can take $\mu(u) = 2$. Neither $s$ nor $u$ can move directly to
its colour in $\beta$, the current colour of the other. So $u$ first rises to $2$, then $s$ moves to $0$, and $u$ moves down
to $1$.

It remains to find a colouring $\mu$ as in Lemma~\ref{lem:um}. For the rest
of the section the instance is also bipartite. It is connected, since every vertex reaches $s$ through out-neighbours. Let $S_0$ be
the side of the bipartition that contains $s$, and $S_1$ the other side. The out-neighbours of a vertex lie on the side
opposite to it.

\begin{lemma}\label{lem:sides}
In a bipartite single-sink instance with $g = 0$, a vertex of $S_0 \setminus \{s\}$ has one of the patterns
$(0,0)$, $(1,1)$, $(2,2)$, $(1,0)$, $(2,0)$, $(1,2)$, and a vertex of $S_1$ one of
$(0,0)$, $(1,1)$, $(2,2)$, $(0,1)$, $(0,2)$, $(2,1)$.
\end{lemma}
\begin{proof}
We use induction along the instance order. For a vertex $v$, we may assume the statement for its out-neighbours, which come
earlier. By Lemma~\ref{lem:s1}, a vertex $v \ne s$ has one of the nine patterns in $\{0,1,2\}^2$. We show that a leaver lies
in $S_1$, a joiner other than $s$ lies in $S_0$, a vertex with the pattern $(2,1)$ lies in $S_1$, and a vertex with the
pattern $(1,2)$ lies in $S_0$.
If $v$ is a leaver, then by Lemma~\ref{lem:s3} it has a joiner out-neighbour, $s$ or a vertex of $S_0$ by induction. Hence
$v \in S_1$. If $v \ne s$ is a joiner, it has a leaver out-neighbour, which lies in $S_1$, and so $v \in S_0$.
If $v$ has the pattern $(2,1)$, then $1 \in L(v)$ since $\beta(v) = 1$. As $\alpha(v) = 2$ is the
least free colour of $L(v)$ in $\alpha$, the colour $1$ is not free at $v$ in $\alpha$, so some out-neighbour $p$ has $\alpha(p) = 1$, and $\beta(p) \ne 1$ since $\beta$ is proper. Thus $p = s \in S_0$,
or $p$ is a joiner other than $s$ or has the pattern $(1,2)$, and then $p \in S_0$ by induction. In either case $v \in S_1$. If $v$ has the pattern
$(1,2)$, then in the same way some out-neighbour $p$ has $\beta(p) = 1 \ne \alpha(p)$. Here $p \ne s$ is a leaver or has the
pattern $(2,1)$. By induction $p \in S_1$, and so $v \in S_0$. This excludes, on each side, exactly the three patterns not listed for it.
\end{proof}

We shall choose $\mu$ greedily, in instance order (Definition~\ref{def:mu}). A
count of colours shows that this can fail only at a vertex on $2$ in $\alpha$ or in $\beta$ whose two out-neighbours take both
$2$ and $3$ in $\mu$. Part (a) of the next lemma rules this out when the vertex is fixed on $2$, and part (b) when it is
not fixed.

\begin{lemma}\label{lem:twofacts}
In a bipartite single-sink instance with $g = 0$,
(a) every out-neighbour of a vertex fixed on $2$ is fixed on $0$ or on $1$;
(b) if a vertex $v$ has two out-neighbours, is not fixed, and is on $2$ in $\alpha$ or in $\beta$, then some
out-neighbour of $v$ is fixed on $0$ or on $1$.
\end{lemma}
\begin{proof}
(a) Let $v$ be fixed on $2$. If $v$ has two out-neighbours, then $L(v) = \{0,1,2,3\}$. In $\alpha$ and in $\beta$, neither $0$ nor $1$ is free
at $v$, so one out-neighbour of $v$ is on $0$ and the other on $1$. If one of them is not fixed, then, since the two out-neighbours have the colours $0$ and $1$ both in $\alpha$ and in $\beta$,
one has the pattern $(0,1)$ and the other $(1,0)$. By Lemma~\ref{lem:sides}, a vertex with the pattern $(0,1)$ lies in $S_1$, and a vertex with the
pattern $(1,0)$ lies in $S_0$ (or is $s \in S_0$). So the two out-neighbours of $v$ would lie on different
sides, which is impossible, as both lie on the side opposite to $v$. Hence both are fixed, on $0$ and on $1$. If $v$ has one out-neighbour $p$, then $L(v)$, with at least three colours, contains $0$ or $1$. No such
colour is free at $v$ in $\alpha$ or in $\beta$, since $2$ is the least free colour of $L(v)$ in both. So $p$ has
it in $\alpha$ and in $\beta$. Since $p$ has a single colour in $\alpha$, $L(v)$ contains exactly one of $0$ and $1$, and $p$ is fixed on it.

(b) As $v$ has two out-neighbours, $L(v) = \{0,1,2,3\}$. Let $c \in \{\alpha, \beta\}$ be a colouring in which $v$ is on~$2$.
Then neither $0$ nor $1$ is free at $v$ in $c$, so one out-neighbour $u_0$ of $v$ has $c(u_0) = 0$ and the other, $u_1$, has
$c(u_1) = 1$. Suppose that neither is fixed. If $c = \alpha$, then $u_0$ is a leaver, and $u_1$ is $s \in S_0$ or has
the pattern $(1,0)$ or $(1,2)$. If $c = \beta$, then $u_0$ is $s \in S_0$ or a joiner, and $u_1$ has the pattern
$(0,1)$ or $(2,1)$. In both cases, by Lemma~\ref{lem:sides}, $u_0$ and $u_1$ lie on different sides, which is impossible as in (a). Hence $u_0$ or $u_1$ is fixed, on $0$ or on $1$.
\end{proof}

\begin{definition}\label{def:mu}
In instance order, put $\mu(s) = x$ and, for $v \ne s$, let $\mu(v)$ be the least colour of $L(v)$ that is at least
$\max(\alpha(v), \beta(v))$ and differs from $\mu(u)$ for every out-neighbour $u$ of $v$.
\end{definition}

\begin{proposition}\label{prop:mu}
In a bipartite single-sink instance with $g = 0$, $\mu$ is well defined, and $\mu(v) = \alpha(v)$ for every fixed vertex $v$.
\end{proposition}
\begin{proof}
We use induction along the instance order. Let $v \ne s$ and $M = \max(\alpha(v), \beta(v))$. By
Lemma~\ref{lem:s1}, $M \le 2$. By the definition of $\mu$, every out-neighbour $u \ne s$ of $v$ has
$\mu(u) \ge \max(\alpha(u), \beta(u))$, and so does $s$ if it is an out-neighbour of $v$, since $\mu(s) = x = \alpha(s)$. Moreover $\alpha(u) \ne \alpha(v)$
and $\beta(u) \ne \beta(v)$.

Let $v$ be fixed on $y$. We show that $\mu(v) = y$, that is, that no out-neighbour $u$ has $\mu(u) = y$. If $y = 0$, then
$\mu(u) = 0$ would force $\alpha(u) = 0 = \alpha(v)$, which is impossible. If $y = 1$, then $\mu(u) = 1$ would force
$\alpha(u) = \beta(u) = 0$, since both are at most $\mu(u)$ and differ from $1$. Then $u$ would be fixed on $0$ (so $u \ne s$), and $\mu(u) = 0$ by induction, a contradiction. If $y = 2$,
then $u$ is fixed on $0$ or $1$ by Lemma~\ref{lem:twofacts}(a), and then $\mu(u) \le 1$ by induction.

Now suppose that $v$ is not fixed. Then $M \ge 1$. We call the colours of $L(v)$ that are at least $M$ the \emph{candidates}. We show
that some candidate differs from $\mu(u)$ for every out-neighbour $u$ of $v$. If $v$ has two out-neighbours, then $L(v) = \{0,1,2,3\}$. For
$M = 1$, the two out-neighbours exclude at most two of the three candidates $1, 2, 3$. For $M = 2$, $v$ is on $2$ in
$\alpha$ or in $\beta$, and Lemma~\ref{lem:twofacts}(b) gives an out-neighbour $u$ fixed on $0$ or on $1$, with $\mu(u) \le 1$ by
induction. The other excludes at most one of the candidates $2, 3$.
If $v$ has one out-neighbour~$u$, then $|L(v)| \ge 3$. For $M = 1$, there are at least two candidates. For $M = 2$, the
colour $2$ is the greedy colour of $v$ in $\alpha$ or in $\beta$, that is, the least colour of $L(v)$ other than the colour
of $u$ in that colouring. So at most one colour of $L(v)$ is less than $2$, since otherwise $0$ and $1$ would both be in $L(v)$, and one of them
would differ from the colour of $u$. As $|L(v)| \ge 3$, $L(v)$ is $\{0,2,3\}$ or
$\{1,2,3\}$, with the candidates $2$ and $3$. For both values of $M$, $u$ excludes at most
one of at least two candidates.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:BIPinst}]
Every edge joins a vertex $v$ to an out-neighbour $u$, with $\mu(v) \ne \mu(u)$ by Definition~\ref{def:mu}. Hence $\mu$ is proper. Also
$\mu(v) \in L(v)$, $\mu \ge \alpha$, $\mu \ge \beta$ and $\mu(s) = x$. Lemma~\ref{lem:um} now gives the required sequence.
\end{proof}

\begin{remark}\label{rem:triangle}
Without bipartiteness, which we used only in Lemmas~\ref{lem:sides} and~\ref{lem:twofacts}, a colouring $\mu$ as in
Lemma~\ref{lem:um} need not exist. Take the sink $s$ with the list $\{0,1\}$
and $x = 1$, and the vertices $u_1, u_2, u_3$ in instance order, with $N^+(u_1) = \{s\}$, $N^+(u_2) = \{u_1\}$, $N^+(u_3) = \{u_1, u_2\}$,
$L(u_1) = L(u_3) = \{0,1,2,3\}$ and $L(u_2) = \{1,2,3\}$. This is a single-sink instance with $g = 0$, whose edges form the
triangle $u_1 u_2 u_3$ and the edge $s u_1$. The patterns of $u_1, u_2, u_3$ are $(0,1)$, $(1,2)$ and $(2,0)$. Such a
$\mu$ would have $\mu(u_1) \ge 1$ and $\mu(u_1) \ne \mu(s) = 1$, and $\mu(u_2), \mu(u_3) \ge 2$. So it
would colour the triangle with the two colours $2$ and~$3$, which is impossible. The conclusion of Lemma~\ref{lem:twofacts}(b)
fails at $u_3$, which has two out-neighbours, is not fixed and is on $2$ in $\alpha$, while neither of its out-neighbours
is fixed. Still, this instance has a sequence as in Theorem~\ref{thm:BIPinst}, in which we recolour $u_1$
to $3$, $s$ to $0$, $u_3$ to $0$, $u_2$ to $2$ and $u_1$ to $1$. In the instance of the first open problem in
Section~\ref{sec:open}, by contrast, some vertex must move three times.
\end{remark}

\begin{proof}[Proof of Theorem~\ref{thm:bip}]
Let $G$ be a bipartite $2$-degenerate graph on $n$ vertices. We choose a degeneracy ordering of $G$. The class $\mathcal{K}$
of bipartite single-sink instances is closed under changing the lists. By Theorem~\ref{thm:BIPinst}, it meets
the condition of Lemma~\ref{lem:sweep} with $\lambda = 2$. Every instance on a cone lies in $\mathcal{K}$: the cone induces a
bipartite subgraph of $G$, and the instance on it is single-sink. Lemma~\ref{lem:sweep} thus gives $\diam \Rk{4}(G) \le 2n(n+1)$.
\end{proof}


\section{Proof of Proposition~\ref{prop:lb}}\label{sec:lb}
We deduce Proposition~\ref{prop:lb} from the bounds in terms of $n$ in Propositions~\ref{prop:LBH} and~\ref{prop:LB6}.
Here $\ell$ is the number of vertices of a path and $n$ that of the whole graph. As before, a \emph{colouring} is a proper
colouring with the colours $0, 1, 2, 3$.


\begin{figure}[t]
\centering
\begin{tikzpicture}[scale=0.72, vtx/.style={circle, fill, inner sep=1.4pt}]
\foreach \i in {1,...,7} \node[vtx] (h\i) at (\i,0) {};
\draw (h1) -- (h2) -- (h3) -- (h4) -- (h5) -- (h6) -- (h7);
\node[vtx, label=above:{$a$}] (ha) at (4,1.6) {};
\node[vtx, label=below:{$b$}] (hb) at (4,-1.6) {};
\foreach \i in {1,3,5,7} \draw (ha) -- (h\i);
\foreach \i in {2,4,6} \draw (hb) -- (h\i);
\node[below left] at (h1) {$v_1$};
\node[below right] at (h7) {$v_7$};
\begin{scope}[xshift=8.5cm]
\foreach \i in {1,...,9} \node[vtx] (j\i) at (\i,0) {};
\draw (j1) -- (j2) -- (j3) -- (j4) -- (j5) -- (j6) -- (j7) -- (j8) -- (j9);
\node[vtx, label=above:{$a_1$}] (ja1) at (5.5,1.9) {};
\node[vtx, label=below:{$a_3$}] (ja3) at (4.5,1.1) {};
\node[vtx, label=below:{$a_2$}] (ja2) at (4,-1.5) {};
\node[vtx, label=below:{$a_0$}] (ja0) at (6,-1.5) {};
\foreach \i in {1,5,9} \draw (ja1) -- (j\i);
\foreach \i in {3,7} \draw (ja3) -- (j\i);
\foreach \i in {2,6} \draw (ja2) -- (j\i);
\foreach \i in {4,8} \draw (ja0) -- (j\i);
\node[below left] at (j1) {$v_1$};
\node[below right] at (j9) {$v_9$};
\end{scope}
\end{tikzpicture}
\caption{The graphs $H_7$ (left, Section~\ref{sec:planar}) and $J_9$ (right, Section~\ref{sec:girth6}).}\label{fig:HJ}
\end{figure}

\subsection{A planar family}\label{sec:planar}
For $\ell \ge 2$, let $H_\ell$ be the path $v_1 v_2 \cdots v_\ell$ together with a vertex $a$ joined to every $v_i$ with $i$ odd and a vertex
$b$ joined to every $v_i$ with $i$ even. It has $n = \ell+2$ vertices. It is planar (Figure~\ref{fig:HJ} draws $H_7$ with $a$ above the path and $b$
below it), $2$-degenerate (in the ordering $v_1, \dots, v_\ell, a, b$ every vertex has at most two later neighbours) and bipartite, with sides
$\{v_i : i \text{ odd}\} \cup \{b\}$ and $\{v_i : i \text{ even}\} \cup \{a\}$. For $\ell \ge 3$ it contains the $4$-cycle
$a v_1 v_2 v_3 a$, so it is not a forest, and its degeneracy is $2$.

\begin{proposition}\label{prop:LBH}
For $\ell \ge 5$, the colourings $\sigma^+$ and $\sigma^-$ of $H_\ell$ ($a$ and $b$ on $3$, $v_i$ on $\pm(i-1) \bmod 3$) are at distance
at least $(\ell-5)^2/8$ in $\Rk{4}(H_\ell)$.
Hence $\diam \Rk{4}(H_\ell) \ge (n-7)^2/8$.
\end{proposition}

We call a colouring \emph{plain} if $a$
and $b$ have the colour $3$. In a plain colouring the path uses only the colours $0,1,2$. For a plain colouring $c$ and $1 \le i < \ell$, the \emph{step}
$\delta_i \in \{+1,-1\}$ is defined by $\delta_i \equiv c(v_{i+1}) - c(v_i) \pmod 3$. A \emph{height function} of $c$ is a function
$h \colon \{1,\dots,\ell\} \to \mathbb{Z}$ with $h(i+1) - h(i) = \delta_i$ for $1 \le i < \ell$. It is the analogue on a path of the height functions of
Section~\ref{sec:setting}, without the condition $h(i) \equiv c(v_i) \pmod 3$. We define the \emph{winding} of $c$ as $W = h(\ell) - h(1)$. It does not depend on the choice of $h$ and is the weight of the path oriented from $v_1$ to $v_\ell$ in the sense of
\cite{CvdHJ11}. For $\sigma^+$ every step is $+1$, and for $\sigma^-$ every step is $-1$.

\begin{lemma}\label{lem:h1}
Let two plain colourings differ by a move of a path vertex $v_i$, and let $h$ be a height function of the first. Then a height
function of the second is obtained from $h$ by changing $h(i)$ by $2$ or by $-2$, as the move determines, and keeping the
other values of $h$.
\end{lemma}
\begin{proof}
Suppose first that $1 < i < \ell$. The new colour of $v_i$ is not $3$ (as $v_i$ is adjacent to $a$ or to $b$, both on $3$), not its old colour, and not the colours of
$v_{i-1}, v_{i+1}$, which also differ from its old colour. As only $0,1,2$ are available, $v_{i-1}$ and $v_{i+1}$ have the same
colour, so $\delta_{i-1} = -\delta_i$. After the move both steps change sign. Thus $h(i)$ changes by $\pm 2$. For
$i \in \{1, \ell\}$, the only path neighbour of $v_i$ has the colour that differs from both the old and the new colour
of $v_i$, so the one step at $v_i$ changes sign, and again $h(i)$ changes by $\pm 2$.
\end{proof}

\begin{lemma}\label{lem:flat}
If a plain colouring $c$ allows a move of $a$ or of $b$, then $|W| \le 4$.
\end{lemma}
\begin{proof}
Let $h$ be a height function of $c$. We call $v_i$ an \emph{odd} or an \emph{even} vertex according to the parity
of $i$. Suppose that $a$ can move to a colour $y \in \{0,1,2\}$. Then every odd vertex has one of the other two
colours, $y_1 \equiv y + 1$ and $y_2 \equiv y + 2 \pmod 3$. Let $u = v_{2j-1}$ and $u' = v_{2j+1}$ be consecutive odd vertices, and $w = v_{2j}$ the even vertex
between them. If $u$ and $u'$ have the same colour, then $h(2j+1) = h(2j-1)$. Otherwise $w$, adjacent to $u$, $u'$
and $b$, has neither $y_1$ nor $y_2$ nor $3$ and thus has $y$. If $u$ is on $y_1$ and $u'$ on $y_2$, the colours $y_1, y_1 - 1, y_1 + 1$ give two
steps $-1$, and $h(2j+1) = h(2j-1) - 2$. If $u$ is on $y_2$ and $u'$ on $y_1$, then $h(2j+1) = h(2j-1) + 2$. Along the odd vertices, changes from $y_1$ to $y_2$
and from $y_2$ to $y_1$ alternate. Hence the
heights of the odd vertices take at most two values, $2$ apart. The first odd vertex is $v_1$ and the last is
$v_\ell$ or $v_{\ell-1}$. Thus $|h(\ell) - h(1)| \le 2 + 1 = 3$. If instead $b$ can move, to a colour $y$, we argue in the same way
with the even vertices. When two consecutive even vertices have different colours, the
odd vertex between them is adjacent to both of them and to $a$, which is on $3$; it therefore has the colour $y$. The
first even vertex is $v_2$ and the last is $v_\ell$ or $v_{\ell-1}$. Thus $|h(\ell) - h(1)| \le 1 + 2 + 1 = 4$.
\end{proof}

The following count shows that a height function with small winding is far from one whose steps are all $+1$.
\begin{lemma}\label{lem:cost}
Let $h, h' \colon \{1,\dots,\ell\} \to \mathbb{Z}$ be functions whose steps $h(i+1) - h(i)$ and $h'(i+1) - h'(i)$ are all
$\pm 1$, every step of $h$ being $+1$. Let a real number $q \ge 0$ satisfy $h'(\ell) - h'(1) \le (\ell-1) - q$ and $q/4 + 1 \le \ell/2$. Then $\sum_i |h'(i) - h(i)| \ge q^2/8$. The same holds with all signs reversed
(all steps of $h$ equal to $-1$ and $h'(\ell) - h'(1) \ge -(\ell-1) + q$).
\end{lemma}
\begin{proof}
Put $f = h' - h$. The steps of $f$ are $0$ or $-2$. Thus $f$ does not increase. Moreover, $f(1) - f(\ell) = (\ell-1) - (h'(\ell) - h'(1)) \ge q$. For
$i \le \ell/2$, put $i' = \ell+1-i$. Then $f$ decreases by at most $2(i-1)$ on $[1,i]$ and on $[i',\ell]$, so
$|f(i)| + |f(i')| \ge f(i) - f(i') \ge q - 4(i-1)$. Let $\kappa = \lfloor q/4 \rfloor$. The indices $i = 1, \dots, \kappa+1$ are at most
$\ell/2$, and the pairs $\{i, i'\}$ for these indices are disjoint. Summing the last inequality over them, writing
$j = i - 1$, and using $\kappa + 1 > q/4$ and $2\kappa \le q/2$, we obtain
\[ \sum_i |f(i)| \ge \sum_{j=0}^{\kappa} (q - 4j) = (\kappa+1)(q - 2\kappa) \ge (q/4)(q/2) = q^2/8. \qedhere \]
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:LBH}]
We consider a sequence of moves in $\Rk{4}(H_\ell)$ from $\sigma^+$ to $\sigma^-$. As long as neither $a$ nor $b$ has moved, all
colourings are plain. By Lemma~\ref{lem:h1}, they have height functions $h_0, h_1, \dots$, where $h_0(i) = i - 1$ and each
$h_{j+1}$ differs from $h_j$ at a single index by $\pm 2$. Each move thus changes $\sum_i |h_j(i) - h_0(i)|$ by at most $2$. If $a$ and $b$ never
move, the last height function, $h'$, has all steps $-1$, and Lemma~\ref{lem:cost} with $q = 2\ell - 4$ (for which $q/4 + 1 =
\ell/2$) gives $\sum_i |h'(i) - h_0(i)| \ge (\ell-2)^2/2$. Hence at least $(\ell-2)^2/4 > (\ell-5)^2/8$ moves are needed, close
to the bound $(\ell^2 - 1)/4$ of \cite{BJLPP14} for $3$-colourings of a path.
Otherwise let $\tau_1 < \tau_2$ be the positions in the sequence of the first and the last move of $a$ or $b$ (there are at
least two such moves, as $\sigma^-$ is plain and each of $a, b$ that leaves the colour $3$ must return to it). Before $\tau_1$ all
colourings are plain. The colouring just before $\tau_1$ allows a move of $a$ or $b$. By Lemma~\ref{lem:flat} its winding is
at most $4 = (\ell-1) - q$, where $q = \ell - 5$ satisfies $q/4 + 1 \le \ell/2$. Let $h^*$ be the function $h_j$ of this colouring. By
Lemma~\ref{lem:cost}, $\sum_i |h^*(i) - h_0(i)| \ge (\ell-5)^2/8$. Thus at least $(\ell-5)^2/16$ moves precede $\tau_1$. Since neither $a$ nor $b$ moves after $\tau_2$ and $\sigma^-$ is plain, all colourings after $\tau_2$ are plain. The
colouring just after $\tau_2$ allows a move of $a$ or $b$, namely the reverse of the move at $\tau_2$. We read the part after $\tau_2$ backwards from $\sigma^-$,
with the height function $i \mapsto 1 - i$ of $\sigma^-$ in place of $h_0$. Lemma~\ref{lem:cost} with all signs reversed then
shows that at least $(\ell-5)^2/16$ moves follow $\tau_2$. The total is at least $(\ell-5)^2/8$.
\end{proof}

\begin{remark}
The graph $H_\ell$ is the fan of \cite{BJLPP14} with its apex split into $a$ and $b$. We know of no earlier use of this
graph in recolouring. Our proof follows the proofs of \cite[Thms.~11 and~12]{BJLPP14}. As in the first of them, the two
colourings have the colours increasing and decreasing cyclically along the path. Where that proof bounds the change per
move of the value of the colouring, a weighted sum over the edges of the path, we bound that of
$\sum_i |h_j(i) - h_0(i)|$. The apex of the fan can move only when the path uses at most two colours, whereas $a$ and $b$ can
move when the path still uses three, so we need Lemma~\ref{lem:flat} to bound the winding.
\end{remark}

\subsection{A family of girth \texorpdfstring{$6$}{6}}\label{sec:girth6}
For $\ell \ge 5$, let $J_\ell$ be the path $v_1 \cdots v_\ell$ together with four vertices $a_0, \dots, a_3$, where $a_j$ is joined to every
$v_i$ with $i \equiv j \pmod 4$. It has $n = \ell + 4$ vertices; Figure~\ref{fig:HJ} shows $J_9$. We obtain $J_\ell$ from $H_\ell$ by splitting $a$ into $a_1$ and $a_3$, and $b$ into $a_0$
and $a_2$, each new vertex keeping every second path neighbour of the old one. This removes the $4$-cycles $a v_i v_{i+1} v_{i+2} a$
and $b v_i v_{i+1} v_{i+2} b$. The graph $J_\ell$ is $2$-degenerate (in the ordering $v_1, \dots, v_\ell, a_0, \dots, a_3$ every vertex has at most two later neighbours)
and bipartite, with sides $\{v_i : i \text{ odd}\} \cup \{a_0, a_2\}$ and $\{v_i : i \text{ even}\} \cup \{a_1, a_3\}$. Its girth
is $6$. As the path is acyclic, every cycle contains some $a_j$, and the $a_j$ are pairwise non-adjacent. A cycle
through exactly one $a_j$ is $a_j v_i \cdots v_{i'} a_j$ with $i < i'$ and $i \equiv i' \equiv j \pmod 4$. Since $i' - i \ge 4$, its length is
at least $6$. A cycle through two or more of the $a_j$ has at least two path vertices between any two of the $a_j$ that are
consecutive on it (each path vertex is joined to exactly one $a_j$). It therefore has at least three vertices for each $a_j$ on
it, and length at least $6$. Finally, the $6$-cycle $a_1 v_1 v_2 v_3 v_4 v_5 a_1$ shows that $J_\ell$ is not a forest, so its degeneracy
is $2$.

\begin{proposition}\label{prop:LB6}
For $\ell \ge 29$, the colourings $\sigma^+$ and $\sigma^-$ of $J_\ell$ (all $a_j$ on $3$, $v_i$ on $\pm(i-1) \bmod 3$) are at distance at least $(\ell-29)^2/128$
in $\Rk{4}(J_\ell)$. Hence $\diam \Rk{4}(J_\ell) \ge (n-33)^2/128$.
\end{proposition}

We define plain colourings (all $a_j$ on $3$), steps, height functions and windings as for $H_\ell$.
Lemma~\ref{lem:h1} holds for $J_\ell$ with the same proof, since every path vertex is adjacent to some $a_j$.

\begin{lemma}\label{lem:flat4}
If a plain colouring $c$ of $J_\ell$ allows a move of some $a_j$, then $|W| \le 3(\ell-1)/4 + 7$.
\end{lemma}
\begin{proof}
Let $h$ be a height function of $c$. The move goes to a colour $y \in \{0,1,2\}$ that no neighbour of $a_j$ has; we write the other two colours as
$y_1 \equiv y + 1$ and $y_2 \equiv y + 2 \pmod 3$. Let $p_0 < \dots < p_r$ be the indices of the path neighbours of $a_j$, so that $p_{t+1} = p_t + 4$,
$p_0 \le 4$ and $p_r \ge \ell-3$. For $0 \le t < r$, let $D_t = h(p_{t+1}) - h(p_t)$. As a sum of four steps, $D_t$ lies in
$\{-4,-2,0,2,4\}$, and $D_t \equiv c(v_{p_{t+1}}) - c(v_{p_t}) \pmod 3$. If $v_{p_t}$ and $v_{p_{t+1}}$ have the same colour, then $D_t = 0$.
A change from $y_1$ to $y_2$ gives $D_t \equiv 1 \pmod 3$ and so $D_t \in \{4, -2\}$. A change from $y_2$ to $y_1$ gives
$D_t \equiv 2 \pmod 3$ and so $D_t \in \{2, -4\}$. Since the two kinds of change alternate, at most
$\lceil r/2 \rceil$ of the $D_t$ equal $4$, and the others are at most $2$:
\[ -(3r+1) \le \sum_t D_t \le 4\lceil r/2 \rceil + 2(r - \lceil r/2 \rceil) \le 3r + 1, \]
where the lower bound follows symmetrically. At most three steps lie before $p_0$, at most three after $p_r$, and $r \le (\ell-1)/4$, so
$|W| \le (3r + 1) + 6 \le 3(\ell-1)/4 + 7$.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:LB6}]
Put $q = (\ell-29)/4 \ge 0$. Then $3(\ell-1)/4 + 7 = (\ell-1) - q$ and $q/4 + 1 \le \ell/2$. If no $a_j$ moves, at least $(\ell-2)^2/4 > (\ell-29)^2/128$ moves
are needed, as for $H_\ell$. Otherwise we argue as in the proof of Proposition~\ref{prop:LBH}, with Lemma~\ref{lem:flat4} in place of
Lemma~\ref{lem:flat}: Lemma~\ref{lem:cost} gives at least $q^2/16$ moves before the first move of a vertex $a_j$ and, read
backwards from $\sigma^-$, at least $q^2/16$ after the last, so at least $q^2/8 = (\ell-29)^2/128$ in all.
\end{proof}


\begin{remark}\label{rem:Jl}
For $\ell \ge 15$, the graph $J_\ell$ lies in none of the classes (i)--(v) of Section~\ref{sec:intro}.
(i) Its treewidth is at least $3$, since it has $K_4$ as a minor: the sets $\{a_1, v_1, v_9, v_{10}, v_{11}\}$,
$\{a_2, v_2\}$, $\{a_3, v_3\}$ and $\{a_0, v_4, \dots, v_8\}$ are disjoint, each induces a connected subgraph, and any
two of them are joined by an edge.
(ii) The vertex $a_1$ has degree at least $4$, with neighbours $v_1$, $v_5$, $v_9$ and $v_{13}$.
(iv)~Its Grundy number is at least $4$, since a first-fit colouring in an order that begins with $v_1, v_4, v_5, v_{10}, v_7, v_8, v_9, a_1$
gives these vertices the colours~$1, 1, 2, 1, 1, 2, 3, 4$.
(v) As $J_\ell$ has $\ell + 4$ vertices and $2\ell - 1$ edges, its maximum average degree is at least
$2(2\ell - 1)/(\ell + 4) > 3$.

It remains to treat (iii), whose class is defined recursively \cite[Section~3]{BJLPP14}. For a vertex $v$, let $N(v)$ be its set of neighbours.
A \emph{separator} of a graph is a set $S$ of vertices whose removal increases the number of components, and
\emph{identifying} two vertices $u$ and $v$ replaces them by one vertex adjacent to all their neighbours. A $3$-colourable
graph is \emph{$3$-colour-dense} if either it is a disjoint union of cliques with at most three vertices each, or it has a
separator $S$ and vertices $u$ and $v$ with these four properties: $u$ and $v$ lie in different components of the graph
minus $S$; $S \subseteq N(v)$; the component $D$ of $u$ in the graph minus $S$ satisfies $|D| = 1$ or $|D \cup S| \le 3$; and
identifying $u$ with $v$ gives a $3$-colour-dense graph.
The graph $J_\ell$ is connected, has more than three vertices and girth $6$, and has minimum degree at least $2$, since each
$v_i$ has a neighbour on the path and a neighbour $a_j$, and each $a_j$ has at least two neighbours on the path. It is not a
disjoint union of cliques, so it suffices to show that no $S$, $u$, $v$ and $D$ have the first three properties. If $|D| = 1$, then $D = \{u\}$ and
$N(u) \subseteq S \subseteq N(v)$; as $u$ has degree at least $2$, $u$ and $v$ have at least two common neighbours, and $J_\ell$ has a cycle of
length $4$. If $|D| \ge 2$, then $|S| \le 1$, since $|D \cup S| \le 3$. The empty set is not a separator of a connected
graph. If $S = \{z\}$, then $D$ consists of two adjacent vertices, each of degree at least $2$ with all its
neighbours in $D \cup S$. So both are adjacent to $z$, and $J_\ell$ has a triangle. Both cases contradict girth $6$.
\end{remark}

\begin{remark}\label{rem:dhoat}
The bipartite distance-hereditary graphs and the bipartite OAT graphs, named in Section~\ref{sec:intro}, lie in the class
(iii). Replacing $3$ by $2$ in the definition of $3$-colour-dense graphs (Remark~\ref{rem:Jl}) gives the $2$-colour-dense
graphs, which are also $3$-colour-dense, by induction on the number of vertices. Among the $2$-colour-dense graphs are the
\emph{semi-false} graphs \cite[Thm.~10]{BJLPP14}, the graphs that can be built from isolated vertices by repeatedly adding a
vertex adjacent to exactly one existing vertex, or a vertex $u$ with $N(u) \subseteq N(v)$ for an existing vertex $v$.
Semi-false graphs include the chordal bipartite graphs (bipartite graphs in
which every cycle of length at least $6$ has a chord) \cite[Thm.~8]{BJLPP14}. A bipartite distance-hereditary graph has no
induced cycle of length at least $6$, since deleting one vertex of such a cycle would leave a connected induced path whose
ends are at distance $2$ in the graph but at least $4$ in the path. Being chordal bipartite, it is semi-false and lies in
(iii).

OAT graphs are built from single vertices by four operations: disjoint unions; joins (the join of two disjoint graphs adds
every edge between them); adding a vertex $u$ with $N(u) \subseteq N(v)$ for an existing vertex $v$; and attaching a clique
$Q$ to a vertex $v$ (joining every vertex of $Q$ to $v$). Each operation adds edges only at a new vertex or between the two
graphs that it combines, so every graph built along the way is an induced subgraph of the final graph. If the final graph
is bipartite, so are all of them. A join in such a construction is of two edgeless graphs, since an edge of one of them
and a vertex of the other would form a triangle. So the join is a complete bipartite graph; it is chordal bipartite and therefore semi-false. Since $Q$ together with $v$ is a clique in a bipartite graph, an attached clique
$Q$ is a single vertex, and attaching it adds a vertex of degree $1$. A disjoint union of two semi-false graphs is semi-false (start from the isolated vertices of both constructions, then perform their two sequences of operations one after the
other),
and adding a vertex $u$ with $N(u) \subseteq N(v)$ keeps a graph semi-false. By induction along the construction, a
bipartite OAT graph is semi-false, and so lies in (iii).
\end{remark}



\section{Open problems}\label{sec:open}
\begin{enumerate}[leftmargin=*,itemsep=2pt,topsep=2pt]
\item Does every instance of Definition~\ref{def:instance} with $g = 0$ and $m$ vertices have a sequence from $\alpha$ to $\beta$ of
 length $O(m)$? By Lemma~\ref{lem:sweep}, a positive answer would prove Conjecture~\ref{conj:cereceda} for $d = 2$ (the case $k \ge 5$ is
 known \cite{Cer07}). When the instance has an odd
 cycle, the colouring $\mu$ need not exist (Remark~\ref{rem:triangle}), and two moves per vertex are not always enough. Take the
 sink $s$ with the list $\{0,1\}$ and $x = 1$, and the vertices $u_1, \dots, u_7$ in instance order, with the
 following out-neighbours and lists:
 \[ \begin{array}{c|ccccccc}
 v & u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & u_7\\ \hline
 N^+(v) & \{s\} & \{s\} & \{u_1\} & \{u_2,u_3\} & \{u_4\} & \{u_4\} & \{u_3,u_6\}\\
 L(v) & \{0,1,2\} & \{0,1,2\} & \{0,2,3\} & \{0,1,2,3\} & \{0,1,2\} & \{1,2,3\} & \{0,1,2,3\}
 \end{array} \]
 This instance contains the $5$-cycle $s u_1 u_3 u_4 u_2 s$.
 In every sequence from $\alpha$ to $\beta$ some vertex moves at least three times \cite[Remark~34.9]{G}.
\item Is $\diam \Rk{4}(G) = O(n^2)$ for every $2$-degenerate graph $G$ of girth at least $5$ on $n$ vertices?
 If so, the graphs of girth $6$ in Proposition~\ref{prop:lb} show that the order $n^2$ is best possible. Is $\diam \Rk{4}(G) = o(n^2)$ for
 $2$-degenerate graphs $G$ of girth at least $7$? We cannot extend the construction of Section~\ref{sec:girth6} to girth $7$ by changing the spacing.
 If, for a spacing $p \ge 2$, each $a_j$
 ($0 \le j < p$) is joined to the path vertices $v_i$ with $i \equiv j \pmod p$, then the girth is at most $6$ once
 $\ell \ge p + 2$. Indeed, if $i + p + 1 \le \ell$ and $j \equiv i \pmod p$, then
 $a_j v_i v_{i+1} a_{j+1} v_{i+p+1} v_{i+p} a_j$ is a cycle of length $6$, where $a_p$ means $a_0$.

 For planar graphs of girth at least $7$, the second question has a positive answer. Such a graph has maximum average
 degree less than $14/5$, and \cite{Feg21} then gives $\diam \Rk{4}(G) = O(n\log^2 n)$. Planar graphs of girth at least $6$
 are $2$-degenerate, and Theorem~\ref{thm:bip} gives $\diam \Rk{4}(G) = O(n^2)$ for those that are bipartite. Bartier,
 Bousquet, Feghali, Heinrich, Moore and Pierron proved that $\diam \Rk{5}(G) = O(n)$ for all of them
 \cite[Thm.~1.7]{BBFHMP23}. They remarked after that theorem that $\Rk{4}(G)$ may also have linear diameter. The graphs
 $J_\ell$ do not rule out this linear bound, as they are not planar for $\ell \ge 9$. By Euler's formula, a planar graph
 of girth $6$ on $n$ vertices has at most $3(n-2)/2$ edges, while $J_\ell$, of girth $6$, has $\ell + 4$ vertices and
 $2\ell - 1 > 3(\ell+2)/2$ edges.
\item The largest diameter $\rho(n)$ of $\Rk{4}(G)$ over bipartite $2$-degenerate graphs $G$ on
 $n$ vertices satisfies $n^2/8 - O(n) \le \rho(n) \le 2n^2 + O(n)$ (Proposition~\ref{prop:lb} and Theorem~\ref{thm:bip}).
 What is
 $\lim_n \rho(n)/n^2$, if it exists?
\item For $d \ge 3$, is $\diam \Rk{d+2}(G) = O(n^2)$ for every bipartite $d$-degenerate graph $G$ on $n$
 vertices? For $d = 3$ this holds for planar bipartite graphs, which are $3$-degenerate \cite{BH22}.
\end{enumerate}

\paragraph{Acknowledgments.}
This work was done overwhelmingly by AI models and supervised by the author. The models were Anthropic's Claude and OpenAI's
ChatGPT. The author takes full responsibility for the paper.

\needspace{10\baselineskip}
\begin{thebibliography}{BBFHMP}\small\setlength{\itemsep}{0pt}
\item[] Where an arXiv or open version is listed, the numbers we cite refer to it.
\bibitem[BBFHMP]{BBFHMP23} V.~Bartier, N.~Bousquet, C.~Feghali, M.~Heinrich, B.~Moore, T.~Pierron, Recoloring planar graphs of
 girth at least five, SIAM J.\ Discrete Math.\ 37 (2023) 332--350; arXiv:2112.00631.
\bibitem[BLM]{BLM21} T.~Biedl, A.~Lubiw, O.~Merkel, Building a larger class of graphs for efficient reconfiguration of vertex
 colouring, in: Extended Abstracts EuroComb 2021, Trends Math.\ 14, Birkh\"auser, 2021, 286--292; full version: arXiv:2003.01818.
\bibitem[BB]{BB18} M.~Bonamy, N.~Bousquet, Recoloring graphs via tree decompositions, European J.\ Combin.\ 69 (2018) 200--213;
 arXiv:1403.6386.
\bibitem[BJLPP]{BJLPP14} M.~Bonamy, M.~Johnson, I.~Lignos, V.~Patel, D.~Paulusma, Reconfiguration graphs for vertex colourings of
 chordal and chordal bipartite graphs, J.\ Comb.\ Optim.\ 27 (2014) 132--143; open version: HAL lirmm-00782882.
\bibitem[BC]{BC09} P.~Bonsma, L.~Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial
 distances, Theoret.\ Comput.\ Sci.\ 410 (2009) 5215--5226; open version: TU Berlin DepositOnce (preprint of 18 May 2007),
 doi:10.14279/depositonce-14393.
\bibitem[BFHR]{BFHR25} N.~Bousquet, L.~Feuilloley, M.~Heinrich, M.~Rabie, Short and local transformations between
 $(\Delta+1)$-colorings, Innov.\ Graph Theory 2 (2025) 119--156; arXiv:2203.08885.
\bibitem[BH]{BH22} N.~Bousquet, M.~Heinrich, A polynomial version of Cereceda's conjecture, J.\ Combin.\ Theory Ser.\ B 155 (2022)
 1--16; arXiv:1903.05619.
\bibitem[BP]{BP16} N.~Bousquet, G.~Perarnau, Fast recoloring of sparse graphs, European J.\ Combin.\ 52 (2016) 1--11;
 arXiv:1411.6997.
\bibitem[Ce]{Cer07} L.~Cereceda, Mixing graph colourings, PhD thesis, London School of Economics, 2007;\newline
 \url{https://researchonline.lse.ac.uk/id/eprint/131216}.
\bibitem[CvdHJ1]{CvdHJ08} L.~Cereceda, J.~van den Heuvel, M.~Johnson, Connectedness of the graph of vertex-colourings,
 Discrete Math.\ 308 (2008) 913--919.
\bibitem[CvdHJ2]{CvdHJ11} L.~Cereceda, J.~van den Heuvel, M.~Johnson, Finding paths between 3-colorings, J.\ Graph Theory 67
 (2011) 69--82.
\bibitem[CM]{CM24} D.~W.~Cranston, R.~Mahmoud, 5-Coloring reconfiguration of planar graphs with no short odd cycles,
 J.\ Graph Theory 105 (2024) 670--679; arXiv:2208.02228.
\bibitem[DFFV]{DFFV06} M.~Dyer, A.~D.~Flaxman, A.~M.~Frieze, E.~Vigoda, Randomly coloring sparse random graphs with fewer colors
 than the maximum degree, Random Structures Algorithms 29 (2006) 450--465.
\bibitem[Feg]{Feg21} C.~Feghali, Reconfiguring colorings of graphs with bounded maximum average degree, J.\ Combin.\ Theory
 Ser.\ B 147 (2021) 133--138; arXiv:1904.12698.
\bibitem[FJP]{FJP16} C.~Feghali, M.~Johnson, D.~Paulusma, A reconfigurations analogue of Brooks' theorem and its consequences,
 J.\ Graph Theory 83 (2016) 340--358; arXiv:1501.05800.
\bibitem[G]{G} D.~Goel, Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite
 2-degenerate graphs, Zenodo (2026), version 2.30, \href{https://doi.org/10.5281/zenodo.23603237}{doi:10.5281/zenodo.23603237}.
\bibitem[GMP]{GMP04} L.~A.~Goldberg, R.~Martin, M.~Paterson, Random sampling of $3$-colorings in $\mathbb{Z}^2$, Random
 Structures Algorithms 24 (2004) 279--302.
\end{thebibliography}

\end{document}