# Kempe Equivalent List Edge-Colorings of Planar Graphs

Daniel W. Cranston Department of Computer Science, Virginia Commonwealth
University, Richmond, VA, USA<EMAIL_ADDRESS>
###### Abstract

For a list assignment $L$ and an $L$-coloring $\varphi$, a Kempe swap in
$\varphi$ is _$L$ -valid_ if it yields another $L$-coloring. Two $L$-colorings
are _$L$ -equivalent_ if we can form one from another by a sequence of
$L$-valid Kempe swaps. And a graph $G$ is _$L$ -swappable_ if every two of its
$L$-colorings are $L$-equivalent. We consider $L$-swappability of line graphs
of planar graphs with large maximum degree. Let $G$ be a planar graph with
$\Delta(G)\geq 9$ and let $H$ be the line graph of $G$. If $L$ is a
$(\Delta(G)+1)$-assignment to $H$, then $H$ is $L$-swappable. Let $G$ be a
planar graph with $\Delta(G)\geq 15$ and let $H$ be the line graph of $G$. If
$L$ is a $\Delta(G)$-assignment to $H$, then $H$ is $L$-swappable. The first
result is analogous to one for $L$-choosability by Borodin, which was later
strengthened by Bonamy. The second result is analogous to another for
$L$-choosability by Borodin, which was later strengthened by Borodin,
Kostochka, and Woodall.

Dedicated to the memory of Landon Rabern.

##  1 Introduction and Main Results

For a graph $G$ with a proper $k$-coloring $\varphi$ and distinct
$i,j\in\\{1,\ldots,k\\}$, an _$(i,j)$ -Kempe swap_ interchanges the colors on
some component of the subgraph induced by colors $i$ and $j$. Performing a
Kempe swap on $\varphi$ yields another proper $k$-coloring of $G$. Kempe swaps
were introduced in the late 1800s in an attempt to prove the 4 Color Theorem.
This inital effort failed, but Heawood largely salvaged the idea, and used it
to prove the 5 Color Theorem. Kempe swaps did play an important role in the
eventual proof of the 4 Color Theorem nearly a century later, and they have
also been a central tool in most work on edge-coloring. Two $k$-colorings are
(Kempe) _$k$ -equivalent_ if we can transform one into the other by a sequence
of Kempe swaps, never using more than $k$ colors. Mohar conjectured that if
$G$ is $k$-regular, then all of its $k$-colorings are $k$-equivalent. This was
proved for $k=3$ by Feghali, Johnson, and Paulusma [10] (with a single
exception, the Cartesian product $K_{3}\\!\\!\\!\\!\\!\qed\,K_{2}$), and for
$k\geq 4$ by Bonamy, Bousquet, Feghali, and Johnson [3].

Here we study edge-coloring; equivalently, this is coloring the line graph.
Vizing proved that $\chi^{\prime}\leq\Delta+1$ for every graph (where
$\chi^{\prime}$ and $\Delta$ denote edge-chromatic number and maximum degree,
respectively). Mohar [14] extracted from Vizing’s proof an algorithm showing
that all $k$-edge-colorings of a graph are $k$-equivalent when
$k\geq\chi^{\prime}+2$. He also asked whether the same result holds when
$k=\chi^{\prime}+1$. This problem was investigated by McDonald, Mohar, and
Scheide [13] for graphs with $\Delta\leq 4$ and by Asratian and Casselgren [1]
for graphs with $\Delta\leq 5$. One consequence of Main Theorem 1 is that we
answer Mohar’s question affirmatively for all planar graphs with $\Delta\geq
9$. One consequence of Main Theorem 2 is that, for all planar graphs with
$\Delta\geq 15$, we get the stronger statement that all $k$-edge-colorings are
$k$-equivalent whenever $k\geq\chi^{\prime}$.

A _list assignment_ $L$ for a graph $G$ gives each vertex $v\in V(G)$ a set of
(allowable) colors $L(v)$, and an _$L$ -coloring_ is a proper coloring
$\varphi$ such that $\varphi(v)\in L(v)$ for all vertices $v$. If $|L(v)|=k$
for all $v\in V(G)$, and some constant $k$, then $L$ is a _$k$ -assignment_.
Historically, Kempe swaps have not been studied for list coloring, since we
encounter the obvious concern that a Kempe swap in a proper $L$-coloring of
$G$ might not yield another proper $L$-coloring of $G$. (Consider a single
edge $vw$ with $L(v)=\\{1,2\\}$, $L(w)=\\{1,3\\}$, $\varphi(v)=1$,
$\varphi(w)=3$, and a 1,3-swap at $w$.) However, we can easily sidestep this
obstacle. A Kempe swap is _valid_ for a graph $G$, list assignment $L$, and
$L$-coloring $\varphi$ if performing that Kempe swap in $\varphi$ yields
another proper $L$-coloring of $G$. For short, we say the swap is _$L$
-valid_††margin:  $L$-valid for $\varphi$. Two $L$-colorings are now _$L$
-equivalent_††margin:  $L$-equivalent if one can be transformed to the other
by a sequence of $L$-valid Kempe swaps, and $G$ is _$L$ -swappable_††margin:
$L$-swappable if every two of its $L$-colorings are $L$-equivalent.111We first
read about $L$-swappability near the end of [9]. For a planar graph $G$ and a
5-assignment $L$ for $G$, Feghali asked whether $G$ is necessarily
$L$-swappable. As far as we know, this question remains open. Cranston and
Mahmoud [7] showed that if $G$ is $k$-regular, with $k\geq 3$, and $L$ is a
$k$-assignment for $G$, then $G$ is $L$-swappable (again with the single
exception of $K_{3}\\!\\!\\!\\!\\!\qed\,K_{2}$).

If $L$ is a list-assignment with $|L(v)|=d(v)$ for all vertices $v$, then $L$
is a _degree assignment_. If, for each degree assignment $L$, graph $G$ has at
least one $L$-coloring, then $G$ is _degree-choosable_. If $G$ is
$L$-swappable whenever $L$ is a degree assignment, then $G$ is _degree-
swappable_. A key step in the proof of Cranston and Mahmoud is showing that if
$H$ is degree-swappable and $H$ is an induced subgraph of $G$, then $G$ is
also degree-swappable. This is perhaps unsurprising, since an analogous result
holds for degree-choosability. However, we should note that being degree-
swappable is more restrictive than being degree-choosable. For example, all
even cycles are 2-choosable. However, if $G$ is a 4-cycle $vwxy$ with
$L(v)=\\{1,2\\}$, $L(w)=\\{2,3\\}$, $L(x)=\\{3,4\\}$, and $L(y)=\\{4,1\\}$,
then $G$ has two $L$-colorings, but neither of these admits any $L$-valid
Kempe swap. Thus, $G$ is not degree-swappable. In fact, no cycle is degree-
swappable. Further, if we begin with any Gallai tree (a connected graph where
each block is an odd cycle or a clique) and add any edge, the resulting graph
is degree-choosable, but is not degree-swappable.

In this paper we investigate the swappability of the line graph $H$ of a graph
$G$, which we typically call the _edge-swappability_ of $G$. We are not aware
of previous work on this problem.222Ito, Kamiński, and Demaine [11] studied a
similar problem, but they only allowed recoloring a single edge at each step,
which is a far more restrictive model. We focus on the case that $G$ is a
simple planar graph. Borodin [4] showed that if such a $G$ has $\Delta(G)\geq
9$, then every $(\Delta(G)+1)$-assignment $L$ to the line graph of $G$ admits
an $L$-coloring. Bonamy [2] later extended this result to such graphs with
$\Delta(G)\geq 8$. Borodin [4] also showed that if $G$ is such a graph with
$\Delta(G)\geq 14$, then every $\Delta(G)$-assignment $L$ to the line graph of
$G$ admits an $L$-coloring. Borodin, Kostochka, and Woodall [5] later extended
this result to such graphs with $\Delta(G)\geq 12$. Here we prove two
analogous results for swappability.

######  Main Theorem 1.

Let $G$ be a simple planar graph with $\Delta(G)\geq 9$. If $H$ is the line
graph of $G$ and $L$ is a $(\Delta(G)+1)$-assignment for $H$, then all
$L$-colorings of $H$ are $L$-equivalent.

######  Main Theorem 2.

Let $G$ be a simple planar graph with $\Delta(G)\geq 15$. If $H$ is the line
graph of $G$ and $L$ is a $\Delta(G)$-assignment for $H$, then all
$L$-colorings of $H$ are $L$-equivalent.

###  1.1 Proof Outline

Figure 1: Left: A short barbell. Center: A non-short barbell. Right: A
$\theta$-graph.

In the rest of this introduction we state our key lemmas and prove our main
results, assuming the lemmas. In Section 2 we prove the lemmas on
swappability. And in Section 3 we use discharging to prove our two structural
lemmas. A _barbell_ ††margin:  barbell is formed from two vertex-disjoint
cycles by identifying one vertex of each cycle with distinct ends of a path;
see Figure 1. We also allow that the path has length 0, in which case we
simply identify one vertex of the first cycle with one vertex of the second;
in this case, the barbell is _short_ ††margin:  short . A _$\theta$
-graph_††margin:  $\theta$-graph is formed from two non-adjacent vertices $v$
and $w$ by adding three internally disjoint $v,w$-paths. A _plane graph_
††margin:  plane graph is a planar graph together with some planar embedding.
For a plane graph $G$, the subgraph _$G_{3}$_ is induced by all edges incident
to vertices of degree 3, and the subgraph _$G_{2}$_ is induced by all edges
incident to vertices of degree 2 that lie on at least one 3-face.††margin:
$G_{3}$, $G_{2}$ Most of our terminology and notation are standard. But, for
completeness, we provide a number of definitions at the end of the
introduction.

Our first lemma was proved by Cranston and Mahmoud [7]. The proof is long, so
we omit it.333Since [7] is not yet published, we include a proof of Lemma 1 in
the appendix. However, in Section 2 we do prove Corollary 2; see Lemma 6. This
is the special case when $H$ is an isolated vertex, which suggests some of the
ideas used to prove the more general case of Lemma 1. For a graph $G$ and
$f:V(G)\to\mathbb{Z}^{+}$, we say $G$ is _$f$ -swappable_††margin:
$f$-swappable if $G$ is $L$-swappable whenever $L$ is a list assignment with
$|L(v)|=f(v)$ for each vertex $v$.

######  Lemma 1.

Fix a graph $G$ and a function $f:V(G)\to\mathbb{Z}^{+}$. Let $H$ be an
induced subgraph of $G$ such that $G-H$ is $f$-swappable. Let
$f^{\prime}(x):=f(x)-(d_{G}(x)-d_{H}(x))$ for all $x\in V(H)$. If
$f^{\prime}(x)\geq d_{H}(x)$ for all $x\in V(H)$ and $H$ is both
$f^{\prime}$-choosable and $f^{\prime}$-swappable, then $G$ is $f$-swappable.

Erdős, Rubin, and Taylor [8] characterized the connected graphs that are not
degree-choosable; these are precisely Gallai trees. So each connected graph
$H$ is $f^{\prime}$-choosable, as in the previous lemma, unless both (a)
$f^{\prime}(v)=d_{H}(v)$ for all $v\in V(H)$ and (b) $H$ is a Gallai tree.

######  Corollary 2.

Fix a graph $G$ and a function $f:V(G)\to\mathbb{Z}^{+}$, and let $v$ be a
vertex with $f(v)>d(v)$. If $G-v$ is $f$-swappable, then $G$ is $f$-swappable.

To prove each of our main results, we assume that it is false and choose $G$
and $L$ to be a counterexample minimizing $\|G\|$. Let $k:=|L(v)|$ for all
vertices $v$. The point of Lemma 1 is that if some subgraph $H$ is
$f^{\prime}$-swappable (and $f^{\prime}$-choosable), then it cannot appear as
an induced subgraph of $G$. If so, then we get that $G-H$ is $f$-swappable by
minimality, and this implies that $G$ is $f$-swappable, by Lemma 1. For a
planar graph $G$, Borodin showed that either (i) $G$ contains a so-called
“light edge”, one incident to fewer than $k$ other edges or (ii) $G$ contains
an even length cycle with each edge incident to $k-2$ edges outside the cycle.
Since neither (i) nor (ii) appears in a minimal counterexample (that is, both
(i) and (ii) are _reducible_), his theorems follows. We can handle (i)
similarly, using Corollary 2. However, the reducibility of (ii) for Borodin’s
theorems relies on the fact that even cycles are 2-choosable. As we noted
above, even cycles are not 2-swappable. Thus, to prove our main theorems, our
structural lemmas must give stronger conclusions. So we replace (ii) with two
larger types of subgraphs (see (C2) and (C3)), each of which contains at least
two instances of (ii).

######  Structural Lemma 1.

If $G$ is a simple plane graph with $\delta\geq 2$, then either

  * (C1)

$G$ contains an edge $vw$ with $d(v)+d(w)\leq\max\\{11,\Delta+2\\}$; or

  * (C2)

$G_{3}$ contains a bipartite barbell (possibly short); or

  * (C3)

$G_{3}$ contains a bipartite $\theta$-graph other than $K_{2,3}$.

######  Structural Lemma 2.

If $G$ is a simple plane graph with $\delta\geq 2$, then either

  * (C1)

$G$ contains an edge $vw$ with $d(v)+d(w)\leq 16$; or

  * (C2)

$G_{2}$ contains a bipartite barbell (possibly short); or

  * (C3)

$G_{2}$ contains either $K_{2,4}$ or a bipartite $\theta$-graph other than
$K_{2,3}$.

When we use Structural Lemma 1 to prove Main Theorem 1, it is straightforward
to show that (C1) and (C2) are reducible, given Lemma 1. The same is true when
using Structural Lemma 2 to Prove Main Theorem 2. However, handling (C3) is
more involved. For now, we simply state the needed result, and use it to prove
our two main theorems. In Section 2, we provide the proof.

######  Lemma 3.

A graph $G$ is degree-swappable whenever it is the line graph of either (1) a
bipartite barbell (possibly short) or (2) a bipartite $\theta$-graph other
than $K_{2,3}$ or (3) $K_{2,4}$.

The following result immediately implies our Main Theorem 1. It is slightly
more technical, so as to better facilitate a proof by minimal counterexample.

######  Theorem 4.

Let $G$ be a simple plane graph, let $J$ be its line graph, and let
$k:=\max\\{10,\Delta+1\\}$. If $L$ is a $k$-assignment for $J$, then $J$ is
$L$-swappable.

###### Proof.

We view $L$ as an edge assignment for $G$, and say that $G$ is _$L$ -edge-
swappable_ to mean that $J$ is $L$-swappable. Suppose the theorem is false;
let $G$ and $L$ be a counterexample minimizing $\|G\|$. Since we are coloring
edges, we assume that $\delta(G)\geq 1$. First suppose that $\delta(G)=1$, and
let $e$ be an edge incident to a 1-vertex. By minimality, $G-e$ is $L$-edge-
swappable. And $e$ is incident to fewer than $|L(e)|$ other edges. So $G$ is
$L$-edge-swappable, by Corollary 2.

Now assume instead that $\delta(G)\geq 2$. By Structural Lemma 1, we know that
either (C1) $G$ contains an edge $vw$ with
$d(v)+d(w)\leq\max\\{11,\Delta+2\\}$; or (C2) $G_{3}$ contains a bipartite
barbell (possibly short); or (C3) $G_{3}$ contains a bipartite $\theta$-graph
other than $K_{2,3}$. First suppose that (C1) holds. By the minimality of $G$,
we know that $G-vw$ is $L$-edge-swappable. Note that
$|L(vw)|=\max\\{10,\Delta+1\\}$, but $vw$ has at most $\max\\{9,\Delta\\}$
incident edges, i.e., $d_{H}(vw)<|L(vw)|$. So, by Corollary 2, we know that
$G$ is $L$-edge-swappable.

Now suppose instead that (C2) or (C3) holds, but (C1) does not. Let $H$ be the
induced subgraph of $G$ in (C2) or (C3), and let $H^{\prime}$ denote the line
graph of $H$. By definition, each edge $vw$ in $G_{3}$ has $d(v)+d(w)\leq
3+\Delta$. Since (C1) does not hold, this inequality holds with equality. That
is, the number of edges incident to $vw$ is exactly $3+\Delta-2=\Delta+1$; so
$d_{J}(vw)=|L(vw)|$. Thus,
$|L(vw)|-(d_{J}(vw)-d_{H^{\prime}}(vw))=d_{H^{\prime}}(vw)$. By Lemma 3, we
know that $H^{\prime}$ is degree-swappable. Hence, Lemma 1 implies that $J$ is
$L$-swappable, i.e., that $G$ is $L$-edge-swappable, as desired. ∎

Our next result immediately implies Main Theorem 2. Similarly to Theorem 4, it
is slightly more technical than Main Theorem 2, to better facilitate a proof
by minimal counterexample.

######  Theorem 5.

Let $G$ be a simple plane graph, let $J$ be its line graph, and let
$k:=\max\\{15,\Delta\\}$. If $L$ is a $k$-assignment for $J$, then $J$ is
$L$-swappable.

We omit the proof of Theorem 5, since it is essentially identical to that of
Theorem 4. The only differences are that we use $G_{2}$ in place of $G_{3}$
and that we use Structural Lemma 2 in place of Structural Lemma 1.

###  1.2 Definitions and Terminology

We write $[k]$ to denote $\\{1,\ldots,k\\}$.††margin:  $[k]$ ††margin:  $|G|$,
$\|G\|$ We write $d(v)$ for the degree of a vertex $v$. For a graph $G$, we
write $|G|$ to denote $|V(G)|$ and write $\|G\|$ to denote $|E(G)|$. We write
$\delta(G)$ for the minimum degree in $G$ and $\Delta(G)$ for the maximum
degree; when $G$ is clear from context, we may simply write $\delta$ or
$\Delta$. A _plane graph_ ††margin:  plane graph is a planar graph along with
some planar embedding. A _$k$ -vertex_††margin:  $k$-vertex is a vertex of
degree $k$, and a _$k$ -neighbor_††margin:  $k$-neighbor (of some vertex $v$)
is an adjacent $k$-vertex. In a plane graph, a $k$-face is a face of length
$k$. The _length_ of a face $f$ is denoted by $\ell(f)$. A _$k^{+}$
-vertex_††margin:  $k^{+}$-vertex (resp.  _$k^{-}$ -vertex_) is a vertex of
degree at least $k$ (resp. at most $k$). We define $k^{+}$-neighbors,
$k^{-}$-neighbors, $k^{+}$-faces, and $k^{-}$-faces analogously. The _line
graph_ $J$ of a graph $G$ has $V(J)=E(G)$ and $e_{1}e_{2}\in E(J)$ if and only
if $e_{1}$ and $e_{2}$ share an endpoint in $G$. The _Cartesian product_ ,
_$G_{1}\\!\\!\\!\\!\\!\qed\,G_{2}$_ ††margin:  $G_{1}\dboxG_{2}$ , of graphs
$G_{1}$ and $G_{2}$ has vertex set $\\{(v,w):v\in V(G_{1}),w\in V(G_{2})\\}$
and $(v_{1},w_{1})$ is adjacent to $(v_{2},w_{2})$ if either (a) $v_{1}=v_{2}$
and $w_{1}w_{2}\in E(G_{2})$ or (b) $w_{1}=w_{2}$ and $v_{1}v_{2}\in
E(G_{1})$.

##  2 Swappability Lemmas

In this section, we prove all of our swappability lemmas. Recall, for a graph
$G$ and a list assignment $L$ for $G$, that $G$ is _$L$ -swappable_††margin:
$L$-swappable if every two of its $L$-colorings $\varphi_{1}$ and
$\varphi_{2}$ are $L$-equivalent. That is, if $\varphi_{1}$ can be transformed
to $\varphi_{2}$ by a sequence of $L$-valid Kempe swaps.

Our first lemma is essentially due to Las Vergnas and Meyniel [12]. They
proved it in the context of coloring, rather than list-coloring, but the proof
for list-coloring is nearly identical. It is a slight reformulation of
Corollary 2 from the introduction.

######  Lemma 6.

Fix a connected graph $G$, a list-assignment $L$ for $G$, and $v\in V(G)$ with
$|L(v)|>d(v)$. If $G-v$ is $L$-swappable, then $G$ is $L$-swappable.

###### Proof.

Let $\varphi_{1}$ and $\varphi_{2}$ denote $L$-colorings of $G$, and let
$\varphi^{\prime}_{1}$ and $\varphi^{\prime}_{2}$ denote their restrictions to
$G^{\prime}$. Since $G^{\prime}$ is $L^{\prime}$-swappable, there exist
$L^{\prime}$-colorings $\psi^{\prime}_{0},\ldots,\psi^{\prime}_{t}$ of
$G^{\prime}$ such that $\psi^{\prime}_{0}=\varphi^{\prime}_{1}$ and
$\psi^{\prime}_{t}=\varphi^{\prime}_{2}$ and $\psi^{\prime}_{i}$ differs from
$\psi^{\prime}_{i-1}$ by a single $L$-valid Kempe swap, for each $i\in[t]$.
Now we use induction on $i$ to extend each $\psi^{\prime}_{i}$ to an
$L$-coloring $\psi_{i}$ of $G$ such that $\psi_{i}$ and $\psi_{i-1}$ are
$L$-equivalent. (The base case, $i=0$, is trivial, since $\psi_{0}^{\prime}$
is a restriction of $\varphi_{1}$.)

Suppose that $\psi^{\prime}_{i}$ differs from $\psi^{\prime}_{i-1}$ by an
$\alpha,\beta$-swap at $v_{i}$, for some $v_{i}\in V(G)\setminus\\{v\\}$ and
some colors $\alpha$ and $\beta$. If $\psi_{i-1}(v)\notin\\{\alpha,\beta\\}$
or if $v$ is not in the same $\alpha,\beta$-component of $\psi_{i-1}$ as
$v_{i}$, then we form $\psi_{i}$ from $\psi_{i-1}$ by performing the same
$\alpha,\beta$-swap at $v_{i}$. This approach also works if
$\\{\alpha,\beta\\}\subseteq L(v)$ and $v$ is in the same
$\alpha,\beta$-component as $v_{i}$, but $v$ has degree 1 in that component.
So suppose $v$ is in the same $\alpha,\beta$-component as $v_{i}$, but either
$|L(v)\cap\\{\alpha,\beta\\}|=1$ or $v$ has degree at least 2 in that
$\alpha,\beta$-component. Since $|L(v)|>d(v)$, there exists $\gamma\in L(v)$
that is unused by $\psi_{i-1}$ on the closed neighborhood of $v$. We first
recolor $v$ with $\gamma$, and then perform the $\alpha,\beta$-swap at
$v_{i}$. As desired, this yields an $L$-coloring $\psi_{t}$ that restricts to
$\psi^{\prime}_{t}$. Finally, if $\psi_{t}(v)\neq\varphi_{2}(v)$, then we
recolor $v$. ∎

Lemma 6 has a number of useful corollaries.

######  Corollary 7.

Let $G$ be a connected graph and $L$ be a list-assignment for $G$. If there
exists a vertex order $\sigma$ such that each vertex is preceded in $\sigma$
by fewer than $|L(v)|$ of its neighbors, then $G$ is $L$-swappable. In
particular, this is true if $|L(v)|\geq d(v)$ for all $v\in V(G)$ and there
exists some vertex $w$ such that $|L(w)|>d(w)$.

###### Proof.

We use induction on $|G|$. The base case, $|G|=1$, is trivial; so assume that
$|G|\geq 2$. Let $v$ denote the final vertex in $\sigma$, let
$G^{\prime}:=G-v$, let $L^{\prime}$ denote $L$ restricted to $G^{\prime}$, and
let $\sigma^{\prime}$ denote $\sigma$ with $v$ deleted. By the induction
hypothesis, $G^{\prime}$ is $L^{\prime}$-swappable. So, by Lemma 6, $G$ is
$L$-swappable. This proves the first statement. The second statement follows
from the first, ordering by non-increasing distance from $w$, since each
vertex $x$ other than $w$ is followed in the order by its neighbor on a
shortest $x,w$-path. ∎

Recall that a _degree assignment_ ††margin:  degree assignment for a graph $G$
is a list assignment $L$ such that $|L(v)|=d(v)$ for all $v\in V(G)$. A graph
is _degree-swappable_ ††margin:  degree-swappable if it is $L$-swappable for
every degree assignment $L$. For a graph $G$ and list-assignment $L$, we
typically let $\mathcal{L}$ denote the set of all $L$-colorings of $G$. For
some $\mathcal{L}^{\prime}\subseteq\mathcal{L}$, we say that
$\mathcal{L}^{\prime}$ _mixes_ if every two $L$-colorings in
$\mathcal{L}^{\prime}$ are $L$-equivalent. For each $v\in V(G)$ and each
$\alpha\in L(v)$, let _$\mathcal{L}_{v,\alpha}$_ ††margin:  mixes
$\mathcal{L}_{v,\alpha}$ denote the set of all $L$-colorings $\varphi$ with
$\varphi(v)=\alpha$. The focus of this section is to prove that various graphs
are degree-swappable.

######  Corollary 8.

Let $L$ be a degree assignment for $G$. Fix $v\in V(G)$ such that $G-v$ is
connected, and fix $\alpha\in L(v)$. If there exists $w\in N(v)$ such that
$\alpha\notin L(w)$, then $\mathcal{L}_{v,\alpha}$ mixes.

###### Proof.

We simply color $v$ with $\alpha$ and apply the second statement of Corollary
7 to $G-v$. ∎

######  Corollary 9.

Let $L$ be a degree assignment for $G$. Fix $v,w,x\in V(G)$ such that $v,x\in
N(w)$ and $vx\notin E(G)$ and $G-v-x$ is connected. If there exists $\alpha\in
L(v)\cap L(x)$, then $\mathcal{L}_{v,\alpha}\cap\mathcal{L}_{x,\alpha}$ mixes.

###### Proof.

We simply color $v$ and $x$ with $\alpha$ and then apply Corollary 7 to
$G-v-x$. ∎

######  Lemma 10.

Let $G$ be a graph with an edge $vw$ and a degree assignment $L$. If $G-vw$ is
degree-choosable and connected and $|L(v)\cap L(w)|\leq 1$, then $G$ is
$L$-swappable.

###### Proof.

Suppose that $L(v)\cap L(w)\subseteq\\{\alpha\\}$, for some color $\alpha$.
Form $L^{\prime}$ from $L$ by removing $\alpha$ from $L(v)$. Form
$L^{\prime\prime}$ from $L$ by removing $\alpha$ from $L(w)$. Let
$\mathcal{L}_{1}$ denote the set of all $L^{\prime}$-colorings of $G-vw$ and
let $\mathcal{L}_{2}$ denote the set of all $L^{\prime\prime}$-colorings of
$G-vw$. Note that $\mathcal{L}_{1}$ mixes, by the second statement of
Corollary 7, since $|L^{\prime}(w)|>d_{G-vw}(w)$. Similarly, $\mathcal{L}_{2}$
mixes. Form $L^{\prime\prime\prime}$ from $L$ by removing $\alpha$ from both
$L(v)$ and $L(w)$. By hypothesis $G-vw$ is degree-choosable, so $G-vw$ has an
$L^{\prime\prime\prime}$-coloring $\varphi$. But $\varphi$ is both an
$L^{\prime}$-coloring and an $L^{\prime\prime}$-coloring. So $\mathcal{L}_{1}$
mixes with $\mathcal{L}_{2}$. Note that every $L$-coloring is either an
$\mathcal{L}_{1}$-coloring or an $\mathcal{L}_{2}$-coloring (or both). Thus,
$G$ is $L$-swappable. ∎

To prove that a graph $G$ is $L$-swappable, we often follow the same approach
as we used to prove the previous lemma. We let $\mathcal{L}$ denote the set of
all $L$-colorings of $G$, and we find sets of $L$-colorings
$\mathcal{L}_{1},\ldots,\mathcal{L}_{t}$ such that
$\mathcal{L}=\bigcup_{i=1}^{t}\mathcal{L}_{i}$. We show that each set
$\mathcal{L}_{i}$ mixes. Finally, for each $i>1$, we show there exists $j<i$
such that $\mathcal{L}_{i}\cap\mathcal{L}_{j}\neq\emptyset$. This proves that
$\mathcal{L}$ mixes, as desired. Often, we choose $\mathcal{L}_{i}$ to be
$\mathcal{L}_{v,\alpha}$ (for some $v$ and $\alpha\in L(v)$) or some other set
that we know mixes by Corollaries 7–9.

The goal of this section is to prove the following lemma, which we stated in
the introduction.

######  Lemma 3.

A graph $G$ is degree-swappable whenever it is the line graph of either (1) a
bipartite barbell (possibly short) or (2) a bipartite $\theta$-graph other
than $K_{2,3}$ or (3) $K_{2,4}$.

We split the proof of this lemma into three parts. In Lemma 11, we handle (1).
In Lemma 12, we handle (3). And in Lemmas 13 and 15, we handle (2).

######  Lemma 11.

The line graph of every bipartite barbell is degree-swappable.

###### Proof.

Consider a (non-short) barbell $G$ that consists of an even cycle $v_{1}\cdots
v_{2s}$, another even cycle $w_{1}\cdots w_{2t}$, and a $v_{1},w_{1}$-path $P$
(possibly of length 1). Let $H$ be the line graph of $G$ and let $L$ be a
degree assignment for $H$. We will show that $H$ is $L$-swappable. Note that
$d_{H}(v_{1}v_{2})=d_{H}(v_{2s}v_{1})=d_{H}(w_{1}w_{2})=d_{H}(w_{2t}w_{1})=3$
and $d_{H}(x)=2$ for all other $x$ of the form $v_{i}v_{i+1}$ or
$w_{j}w_{j+1}$. Denote $L(v_{2}v_{3})$ by $\\{a,b\\}$. By Lemma 10, we assume
that $L(v_{i}v_{i+1})=\\{a,b\\}$ for all $i\in\\{2,\ldots,2t-1\\}$. Further,
$L(v_{1}v_{2})=\\{a,b,c\\}$ for some color $c$. Note that
$\mathcal{L}_{v_{1}v_{2},c}$ mixes, by Corollary 8. If
$\varphi(v_{1}v_{2})=a$, then $\varphi(v_{2i}v_{2i+1})=b$ and
$\varphi(v_{2i+1}v_{2i+2})=a$ for all $i\in[s-1]$. We first color $v_{1}v_{2}$
and $v_{2s-1}v_{2s}$ with $a$, and next apply Corollary 9 to
$H-\\{v_{2}v_{3},\ldots,v_{2s-2}v_{2s-1}\\}$. Thus,
$\mathcal{L}_{v_{1}v_{2},a}$ mixes. Similarly, $\mathcal{L}_{v_{1}v_{2},b}$
mixes. Denote $L(w_{1}w_{2})$ by $\\{a^{\prime},b^{\prime},c^{\prime}\\}$. By
symmetry, each of $\mathcal{L}_{w_{1}w_{2},a^{\prime}}$,
$\mathcal{L}_{w_{1}w_{2},b^{\prime}}$, and
$\mathcal{L}_{w_{1}w_{2},c^{\prime}}$ mixes.

$w_{1}$$w_{2}$$w_{3}$$w_{4}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$abc$$ab$$ab$$ab?$$a^{\prime}b^{\prime}c^{\prime}$$a^{\prime}b^{\prime}$$a^{\prime}b^{\prime}$$a^{\prime}b^{\prime}?$
Figure 2: A non-short barbell, its line graph, and (most of) a degree-
assignment for the line graph.

Finally, if $\alpha\in L(v_{1}v_{2})$, $\beta\in L(w_{1}w_{2})$, then
$\mathcal{L}_{v_{1}v_{2},\alpha}\cap\mathcal{L}_{w_{1}w_{2},\beta}\neq\emptyset$,
as follows. If $\alpha=c$, then we color $v_{1}v_{2}$ with $\alpha$, color
$w_{1}w_{2}$ with $\beta$, and color greedily in order of non-increasing
distance from $v_{2}v_{3}$ (in the uncolored subgraph), since $\alpha\notin
L(v_{2}v_{3})$. So instead assume that $\alpha\in\\{a,b\\}$. Now we color
$v_{1}v_{2},v_{2}v_{3},\ldots,v_{2s-1}v_{2s}$, alternating $a$ and $b$, color
$w_{1}w_{2}$ with $\beta$, and color greedily in order of non-increasing
distance from $v_{2s}v_{1}$. So
$\mathcal{L}_{v_{1}v_{2},\alpha}\cap\mathcal{L}_{w_{1}w_{2},\beta}\neq\emptyset$.
Thus, $\mathcal{L}$ mixes.

Now consider a short barbell. The proof is similar. The main differences are
that $d_{H}(v_{1}v_{2})=d_{H}(w_{1}w_{2})=4$ and that $v_{1}v_{2}$ and
$w_{1}w_{2}$ are adjacent. However, given distinct $\alpha_{1},\alpha_{2}\in
L(v_{1}v_{2})$, there exists $\beta\in
L(w_{1}w_{2})\setminus\\{\alpha_{1},\alpha_{2}\\}$. Further,
$\mathcal{L}_{v_{1}v_{2},\alpha_{1}}\cap\mathcal{L}_{w_{1}w_{2},\beta}\neq\emptyset$
and
$\mathcal{L}_{v_{1}v_{2},\alpha_{2}}\cap\mathcal{L}_{w_{1}w_{2},\beta}\neq\emptyset$.
Thus, $\bigcup_{\alpha\in L(v_{1}v_{2})}\mathcal{L}_{v_{1}v_{2},\alpha}$
mixes. But this includes all of $\mathcal{L}$. So, $H$ is degree-swappable, as
desired. ∎

Observe that the line graph of $K_{2,4}$ is $K_{4}\\!\\!\\!\\!\\!\qed\,K_{2}$.
Thus, the next lemma proves (3) in Lemma 3.

######  Lemma 12.

The graph $K_{4}\\!\\!\\!\\!\\!\qed\,K_{2}$ is 4-swappable.

###### Proof.

Let $G:=K_{4}\\!\\!\\!\\!\\!\qed\,K_{2}$ and let $L$ be a 4-assignment for
$G$. We denote $V(G)$ by $\\{v_{1},v_{2},v_{3},v_{4},$
$w_{1},w_{2},w_{3},w_{4}\\}$ such that $E(G)=\\{v_{i}w_{i}$ for all
$i\in[4]\\}\cup\\{v_{i}v_{j}$ for all distinct $i,j\in[4]\\}\cup\\{w_{i}w_{j}$
for all distinct $i,j\in[4]\\}$; see Figure 3. It is convenient to note that
$K_{4}\\!\\!\\!\\!\\!\qed\,K_{2}$ is 4-connected; given distinct $i,j\in[4]$,
it is easy to find 4 internally-disjoint $v_{i},w_{j}$-paths. Thus, whenever
we color at most 3 vertices, the uncolored subgraph is connected.

Suppose there exist distinct $i,j\in[4]$ such that $L(v_{i})\neq L(w_{j})$. We
will show that $\mathcal{L}$ mixes. By symmetry, assume that $i=1$ and $j=2$.
Let $A:=L(v_{1})\cap L(w_{2})$, let $A_{1}:=L(w_{1})\cap A$, let
$A_{2}:=L(v_{2})\cap A$, let $B_{1}:=L(w_{1})\setminus A$, and let
$B_{2}:=L(v_{2})\setminus A$. So $L(w_{1})=A_{1}\cup B_{1}$ and
$L(v_{2})=A_{2}\cup B_{2}$. For each $\alpha\in B_{1}$, the set
$\mathcal{L}_{w_{1},\alpha}$ mixes, by Corollary 8, since $\alpha\notin A$.
Similarly, for each $\alpha\in B_{2}$, the set $\mathcal{L}_{v_{2},\alpha}$
mixes, again since $\alpha\notin A$. Furthermore, for every $\alpha_{1}\in
B_{1}$ and $\alpha_{2}\in B_{2}$, there exists an $L$-coloring $\varphi$ with
$\varphi(w_{1})=\alpha_{1}$ and $\varphi(v_{2})=\alpha_{2}$, since
$G-w_{1}-v_{2}$ is degree-choosable. Let
$\mathcal{C}_{1}:=\left(\bigcup_{\alpha_{1}\in
B_{1}}\mathcal{L}_{w_{1},\alpha_{1}}\right)\cup\left(\bigcup_{\alpha_{2}\in
B_{2}}\mathcal{L}_{v_{2},\alpha_{2}}\right)$, and note that $\mathcal{C}_{1}$
mixes. For each $\alpha\in A_{1}\cap A_{2}$, the set
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{v_{2},\alpha}$ mixes, by Corollary
9 (however, possibly $A_{1}\cap A_{2}=\emptyset$). Since $|L(v_{1})\cup
L(w_{2})|\geq 5>(|L(w_{1})|+|L(v_{2})|)/2$, there exists $\beta\in
L(v_{1})\cup L(w_{2})\setminus(L(v_{2})\cap L(w_{1}))$. By symmetry, assume
that $\beta\in L(v_{1})$. Now $\mathcal{L}_{v_{1},\beta}$ mixes. Further, for
each $\alpha\in A_{1}\cap A_{2}$, note that
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{v_{2},\alpha}\cap\mathcal{L}_{v_{1},\beta}\neq\emptyset$.
Let $\mathcal{C}_{2}:=\bigcup_{\alpha\in A_{1}\cap
A_{2}}(\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{v_{2},\alpha})$ and note
that $\mathcal{C}_{2}$ mixes (again, if $A_{1}\cap A_{2}=\emptyset$, then
$\mathcal{C}_{2}=\emptyset$, but the statements above and below still hold,
trivially). Since $\beta\notin L(v_{2})\cap L(w_{1})$, there exists
$\gamma\in(B_{1}\cup B_{2})\setminus\\{\beta\\}$. If $\gamma\in B_{1}$, then
$\mathcal{L}_{v_{1},\beta}\cap\mathcal{L}_{w_{1},\gamma}\neq\emptyset$ (since
$G-v_{1}-w_{1}$ is degree-choosable). And if $\gamma\in B_{2}$, then
$\mathcal{L}_{v_{1},\beta}\cap\mathcal{L}_{v_{2},\gamma}\neq\emptyset$. Thus,
$\mathcal{C}_{1}\cup\mathcal{C}_{2}$ mixes.

$v_{1}$$v_{2}$$A_{2}\cup B_{2}$$w_{1}$$A_{1}\cup B_{1}$$w_{2}$ Figure 3:
$K_{4}\\!\\!\\!\\!\\!\qed\,K_{2}$, along with a partition of $L(v_{2})$ and
$L(w_{1})$.

Finally, consider a coloring $\varphi$ with $\varphi(w_{1}),\varphi(v_{2})\in
A$ and $\varphi(w_{1})\neq\varphi(v_{2})$. Let $\alpha_{1}:=\varphi(w_{1})$
and $\alpha_{2}:=\varphi(v_{2})$. First suppose there exists $i\in\\{3,4\\}$
such that $\varphi(v_{i})=\alpha_{1}$; by symmetry, assume that
$\varphi(v_{3})=\alpha_{1}$. Now
$\mathcal{L}_{w_{1},\alpha_{1}}\cap\mathcal{L}_{v_{3},\alpha_{1}}$ mixes and,
for each $\beta\in B_{2}$, there exists
$\varphi^{\prime}\in\mathcal{L}_{w_{1},\alpha_{1}}\cap\mathcal{L}_{v_{3},\alpha_{1}}\cap\mathcal{L}_{v_{2},\beta}$.
Since $\varphi^{\prime}\in\mathcal{C}_{1}$, we are done. Otherwise, there
exists $i\in\\{3,4\\}$ such that $\varphi(v_{i})\notin L(v_{1})$; by symmetry,
assume $i=3$, and let $\beta:=\varphi(v_{3})$. Now $\mathcal{L}_{v_{3},\beta}$
mixes, and for each $\gamma\in B_{1}$, we have
$\mathcal{L}_{v_{3},\beta}\cap\mathcal{L}_{w_{1},\gamma}\neq\emptyset$. Since
$\mathcal{L}_{w_{1},\gamma}$ mixes and is contained in $\mathcal{C}_{1}$, we
are done. This concludes the case that $L(v_{i})\neq L(w_{j})$ for some
distinct $i,j\in[4]$. So we have
$L(v_{1})=L(w_{2})=L(v_{4})=L(w_{1})=L(v_{3})=L(w_{4})=L(v_{2})=L(w_{3})$.
That is, all lists are identical. Let $A:=L(v_{1})$.

Now we show that for each distinct pair $i,j\in[4]$ the set of all
$L$-colorings with $\varphi(v_{i})=\varphi(w_{j})$ mixes, and thus the set of
all $L$-colorings mixes. More precisely, fix $\alpha\in A$. Clearly
$\mathcal{L}_{v_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha}$ mixes. Also, fix
distinct $k,\ell\in[4]$ such that $k\neq i$ and $\ell\neq j$, and fix
$\beta\in A\setminus\\{\alpha\\}$. Now there exists an $L$-coloring $\varphi$
with $\varphi(v_{i})=\varphi(w_{j})=\alpha$ and
$\varphi(v_{k})=\varphi(w_{\ell})=\beta$. This implies that
$\bigcup_{\alpha\in
A}(\mathcal{L}_{v_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha})$ mixes; so let
$D_{i,j}:=\bigcup_{\alpha\in
A}(\mathcal{L}_{v_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha})$. Finally,
$D_{1,2}$ mixes with $D_{2,3}$, which mixes with $D_{1,4}$, which mixes with
$D_{3,2}$, which mixes with $D_{1,3}$. Now we are done, since every
$L$-coloring of $G$ lies in $D_{1,2}\cup D_{1,3}\cup D_{1,4}$. That is,
$\mathcal{L}$ mixes. ∎

######  Lemma 13.

If $G$ is a bipartite $\theta$-graph, with one of its three edge-disjoint
paths of length 1, then the line graph of $G$ is degree-swappable.

###### Proof.

Let $H$ be the line graph of $G$. Now $H$ has four 3-vertices; call these
$v_{1},v_{2},w_{1},w_{2}$, so that $v_{1}w_{1},v_{2}w_{2}\in E(H)$; see Figure
4. Let $x_{1},\ldots$ denote the internal 2-vertices of a $v_{1},v_{2}$-path
of even length, and let $y_{1},\ldots$ denote the internal 2-vertices of a
$w_{1},w_{2}$-path of even length. Denote the sole 4-vertex by $z$, where
$N_{H}(z)=\\{v_{1},v_{2},w_{1},w_{2}\\}$. Denote $L(x_{1})$ by $\\{a,b\\}$. By
Lemma 10, we assume that $L(x_{i})=\\{a,b\\}$ for all $i$, that
$L(v_{1})=\\{a,b,c_{1}\\}$, and that $L(v_{2})=\\{a,b,c_{2}\\}$, for some
colors $c_{1}$ and $c_{2}$. Let
$\mathcal{L}_{1}:=\mathcal{L}_{v_{1},a}\cap\mathcal{L}_{v_{2},a}$ and
$\mathcal{L}_{2}:=\mathcal{L}_{v_{1},b}\cap\mathcal{L}_{v_{2},b}$. By
Corollary 9, both $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ mix. Note that
$\mathcal{L}_{v_{1},c_{1}}$ mixes by Corollary 8, as does
$\mathcal{L}_{v_{2},c_{2}}$. Let
$\mathcal{L}_{3}:=\mathcal{L}_{v_{1},c_{1}}\cup\mathcal{L}_{v_{2},c_{2}}$. If
we color $v_{1}$ with $c_{1}$ and color $v_{2}$ with $c_{2}$, then we can
extend to an $L$-coloring, since the even cycle induced by $w_{1},w_{2},z$,
and the $y_{i}$’s is 2-choosable. Thus, $\mathcal{L}_{3}$ mixes. Note also
that $\mathcal{L}_{1},\mathcal{L}_{2},\mathcal{L}_{3}$ partition
$\mathcal{L}$.

By symmetry, between the $v_{i}$’s and $w_{i}$’s and the $x_{i}$’s and
$y_{i}$’s, we assume there exist colors
$a^{\prime},b^{\prime},c_{1}^{\prime},c_{2}^{\prime}$ such that
$L(y_{i})=\\{a^{\prime},b^{\prime}\\}$,
$L(w_{1})=\\{a^{\prime},b^{\prime},c_{1}^{\prime}\\}$, and
$L(w_{2})=\\{a^{\prime},b^{\prime},c_{2}^{\prime}\\}$. Analogous to
$\mathcal{L}_{1},\mathcal{L}_{2},\mathcal{L}_{3}$, we define
$\mathcal{L}_{4},\mathcal{L}_{5},\mathcal{L}_{6}$, which each mix and which
also partition $\mathcal{L}$. Since there exists an $L$-coloring in
$\mathcal{L}_{3}\cap\mathcal{L}_{6}$, we note that
$\mathcal{L}_{3}\cup\mathcal{L}_{6}$ mixes. By symmetry between $a$ and $b$,
we assume that $c_{1}^{\prime}\neq a$. So there exists some $L$-coloring in
$\mathcal{L}_{1}\cap\mathcal{L}_{6}$. Similarly, there exists some
$L$-coloring in $\mathcal{L}_{3}\cap\mathcal{L}_{4}$. So
$\mathcal{L}_{1}\cup\mathcal{L}_{3}\cup\mathcal{L}_{4}\cup\mathcal{L}_{6}$
mixes. Finally, either $b\neq a^{\prime}$ or $b\neq c_{1}^{\prime}$. In the
first case, there exists a coloring in $\mathcal{L}_{2}\cap\mathcal{L}_{4}$;
in the second, there exists a coloring in
$\mathcal{L}_{2}\cap\mathcal{L}_{6}$. So $\mathcal{L}_{2}$ mixes with
$\mathcal{L}_{1}\cup\mathcal{L}_{3}\cup\mathcal{L}_{4}\cup\mathcal{L}_{6}$.
Since $\mathcal{L}_{1}$, $\mathcal{L}_{2}$, $\mathcal{L}_{3}$ partitions
$\mathcal{L}$, we are done. ∎

$v_{1}$$abc_{1}$$v_{2}$$abc_{2}$$x_{1}$$ab$$z$$w_{1}$$a^{\prime}b^{\prime}c^{\prime}_{1}$$w_{2}$$a^{\prime}b^{\prime}c^{\prime}_{2}$$y_{1}$$a^{\prime}b^{\prime}$
Figure 4: A $\theta$-graph with a path of length 1, its line graph, and (most
of) a list assignment for the line graph.

######  Definition 14.

A _prism_ consists of three vertex disjoint paths $v_{1}\cdots w_{1}$,
$v_{2}\cdots w_{2}$, and $v_{3}\cdots w_{3}$, each of length at least 1, such
that $\\{v_{1},v_{2},v_{3}\\}$ and $\\{w_{1},w_{2},w_{3}\\}$ each induce
$K_{3}$ and all interior vertices of the paths have degree 2. We denote the
$v_{i},w_{i}$-path by $P_{i}$ for each $i\in[3]$. See Figure 5.

If each of three edge-disjoint paths in a $\theta$-graph $G$ has length at
least 2, then the line graph of $G$ is a prism. Thus, Lemmas 13 and 15 imply
(2) in Lemma 3.

######  Lemma 15.

If $G$ is a prism other than $K_{3}\\!\\!\\!\\!\\!\qed\,K_{2}$, then $G$ is
degree-swappable.

###### Proof.

Fix a degree-assignment $L$ for $G$. Note, for each $st\in E(G)$, that $G-st$
is connected and contains a $\theta$-graph; thus it is degree-choosable. So,
by Lemma 10, we assume $|L(s)\cap L(t)|\geq 2$ for all $st\in E(G)$. We label
the vertices as in Definition 14; see Figure 5. We show that we can assume
that $L(v_{1})=L(v_{2})=L(v_{3})$ (and similarly, that
$L(w_{1})=L(w_{2})=L(w_{3})$). Suppose the contrary.

First suppose that $|L(v_{1})\cap L(v_{2})\cap L(v_{3})|=2$. We assume that
$L(v_{1})=\\{a,b,c_{1}\\}$, $L(v_{2})=\\{a,b,c_{2}\\}$, and
$L(v_{3})=\\{a,b,c_{3}\\}$ where possibly $c_{1}=c_{2}$, but $c_{1}\neq c_{3}$
and $c_{2}\neq c_{3}$; see the center of Figure 5. Now
$\mathcal{L}_{v_{1},c_{1}}$ mixes, by Corollary 8, since $v_{1}\in N(v_{3})$,
but $c_{1}\notin L(v_{3})$. Similarly, $\mathcal{L}_{v_{2},c_{2}}$ mixes and
$\mathcal{L}_{v_{3},c_{3}}$ mixes. Further,
$\mathcal{L}_{v_{1},c_{1}}\cap\mathcal{L}_{v_{3},c_{3}}\neq\emptyset$. To see
this, first color $v_{1}$ and $v_{3}$ as prescribed and then color greedily in
order of non-increasing distance from $v_{2}$; we can color $v_{2}$ last since
$v_{3}\in N(v_{2})$, but $\varphi(v_{3})\notin L(v_{2})$. Similarly,
$\mathcal{L}_{v_{2},c_{2}}\cap\mathcal{L}_{v_{3},c_{3}}\neq\emptyset$. Thus
$\mathcal{L}_{v_{1},c_{1}}\cup\mathcal{L}_{v_{3},c_{3}}$ mixes and
$\mathcal{L}_{v_{2},c_{2}}\cup\mathcal{L}_{v_{3},c_{3}}$ mixes. Since
$\mathcal{L}_{v_{1},c_{1}}\cup\mathcal{L}_{v_{2},c_{2}}\cup\mathcal{L}_{v_{3},c_{3}}=\mathcal{L}$,
we conclude that $\mathcal{L}$ mixes when $|L(v_{1})\cap L(v_{2})\cap
L(v_{3})|=2$.

Now suppose instead that $|L(v_{1})\cap L(v_{2})\cap L(v_{3})|=1$. By possibly
renaming colors we assume that $L(v_{1})=\\{a,b_{2},b_{3}\\}$,
$L(v_{2})=\\{a,b_{1},b_{3}\\}$, and $L(v_{3})=\\{a,b_{1},b_{2}\\}$, where
$b_{1},b_{2},b_{3}$ are distinct; again, see Figure 5. Now
$\mathcal{L}_{v_{i},b_{j}}$ mixes by Corollary 8, whenever $i\in[3]$ and
$b_{j}\in L(v_{i})$. Arguments similar to those above show that
$\mathcal{L}_{v_{1},b_{2}}\cup\mathcal{L}_{v_{2},b_{3}}\cup\mathcal{L}_{v_{3},b_{1}}$
mixes. Similarly,
$\mathcal{L}_{v_{1},b_{3}}\cup\mathcal{L}_{v_{2},b_{1}}\cup\mathcal{L}_{v_{3},b_{2}}$
mixes. So $\mathcal{L}$ forms at most 2 equivalence classes. We must show that
it forms only a single equivalence class. Since $G\neq
K_{3}\\!\\!\\!\\!\\!\qed\,K_{2}$, some vertex in $\\{v_{1},v_{2},v_{3}\\}$ has
a 2-neighbor. By symmetry, we assume that it is $v_{1}$, and we call its
2-neighbor $x$. Pick $\alpha\in L(v_{1})\setminus L(x)$. Now
$\mathcal{L}_{v_{1},\alpha}$ mixes. Further,
$\mathcal{L}_{v_{1},\alpha}\cap\mathcal{L}_{v_{2},b_{1}}\neq\emptyset$ and
$\mathcal{L}_{v_{1},\alpha}\cap\mathcal{L}_{v_{3},b_{1}}\neq\emptyset$. Thus,
$\mathcal{L}$ mixes when $|L(v_{1})\cap L(v_{2})\cap L(v_{3})|=1$. Hence, as
desired, we conclude that $|L(v_{1})\cap L(v_{2})\cap L(v_{3})|=3$, i.e.,
$L(v_{1})=L(v_{2})=L(v_{3})$. By symmetry, we also have
$L(w_{1})=L(w_{2})=L(w_{3})$.

Suppose that $L(v_{1})\neq L(w_{1})$. Since $G$ is a prism other than
$K_{3}\\!\\!\\!\\!\\!\qed\,K_{2}$, some $v_{i}$ has a 2-neighbor. By symmetry
among $v_{1},v_{2},v_{3}$, we assume that $v_{1}$ has a 2-neighbor. For each
2-vertex $x$ on the path from $v_{1}$ to $w_{1}$, we assume, by Lemma 10, that
$L(x)\subseteq L(v_{1})$ and $L(x)\subseteq L(w_{1})$. Thus, $L(v_{1})\cap
L(w_{1})=L(x)$. By symmetry, we assume that $L(v_{1})=\\{a,b,c\\}$ and
$L(w_{1})=\\{a,b,d\\}$. Fix $i,j\in[3]$. By Corollary 8, each of
$\mathcal{L}_{v_{i},c}$ and $\mathcal{L}_{w_{j},d}$ mixes. Further,
$\mathcal{L}_{v_{i},c}\cup\mathcal{L}_{w_{j},d}$ mixes, as follows. If $i\neq
j$, then we construct an $L$-coloring $\varphi$ with $\varphi(v_{i})=c$ and
$\varphi(w_{j})=d$, by coloring $v_{i}$ and $w_{j}$ as desired, and then
coloring greedily in order of non-increasing distance from $v_{j}$. Suppose
instead that $i=j$. Now there exist $L$-colorings $\varphi_{1}$,
$\varphi_{2}$, and $\varphi_{3}$ with $\varphi_{1}(v_{i})=c$ and
$\varphi_{1}(w_{i+1})=d$, with $\varphi_{2}(w_{i+1})=d$ and
$\varphi_{2}(v_{i+2})=c$, and with $\varphi_{3}(v_{i+2})=c$ and
$\varphi_{3}(w_{i})=d$ (with all subscripts modulo 3). Thus,
$\mathcal{L}_{v_{i},c}\cup\mathcal{L}_{w_{i},d}$ mixes. But every $L$-coloring
$\varphi$ has $\varphi(v_{i})=c$ for some $i$ and has $\varphi(w_{j})=d$ for
some $j$. Thus, $\mathcal{L}$ mixes when $L(v_{1})\neq L(w_{1})$. So we assume
that $L(v_{1})=L(w_{1})$. By the previous paragraph, this implies that
$L(s)=\\{a,b,c\\}$ for every 3-vertex $s$.

Now we consider three cases, depending on the number of $i\in[3]$ such that
the $v_{i},w_{i}$-path $P_{i}$ has length longer than 1. By symmetry, we
assume that $\ell(P_{1})\geq\ell(P_{2})\geq\ell(P_{3})$; so $\ell(P_{1})>1$,
since $G$ is a prism other than $K_{2}\\!\\!\\!\\!\\!\qed\,K_{3}$. Recall that
all interior vertices on each $P_{i}$ have the same list, that this list is
contained in $L(v_{i})$, and that $L(w_{i})=L(v_{i})$.

$v_{1}$$v_{2}$$v_{3}$$w_{1}$$w_{2}$$w_{3}$$v_{1}$$abc_{1}$$v_{2}$$abc_{2}$$v_{3}$$abc_{3}$$v_{1}$$ab_{2}b_{3}$$v_{2}$$ab_{1}b_{3}$$v_{3}$$ab_{1}b_{2}$
Figure 5: Left: A prism $G$. Center and right: List assignments for $v_{1}$,
$v_{2}$, $v_{3}$ such that $|L(v_{1})\cap L(v_{2})\cap L(v_{3})|=2$ and
$|L(v_{1})\cap L(v_{2})\cap L(v_{3})|=1$, respectively.

Case 1: $\bm{\ell(P_{1})>\ell(P_{2})=\ell(P_{3})=1}.$ By symmetry, we assume
that $L(x)=\\{a,b\\}$ for each interior vertex $x$ of $P_{1}$. Now
$\mathcal{L}_{v_{1},c}$ and $\mathcal{L}_{w_{1},c}$ each mix. Further,
$\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{w_{1},c}\neq\emptyset$, so
$\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{w_{1},c}$ mixes. Suppose instead, by
symmetry, that $\varphi(v_{1})=a$ and $\varphi(w_{1})\neq c$. Performing an
$a,c$-swap at $v_{1}$ yields an $L$-coloring $\varphi^{\prime}$ with
$\varphi^{\prime}(v_{1})=c$. This is because $\\{a,c\\}\subseteq L(s)$ for
every 3-vertex $s$ and either $\varphi(w_{1})=b$ or $\varphi(x)=b$, where $x$
is the neighbor of $w_{1}$ on $P_{1}$. So $\mathcal{L}$ mixes.

Case 2: $\bm{\ell(P_{1})\geq\ell(P_{2})>\ell(P_{3})=1.}$ By symmetry, we
assume that $L(x)=\\{a,b\\}$ for each interior vertex $x$ of $P_{1}$. Suppose
also that $L(y)=\\{a,b\\}$ for each interior vertex $y$ of $P_{2}$. Now
$\mathcal{L}_{s,c}$ mixes for each $s\in\\{v_{1},v_{2},w_{1},w_{2}\\}$.
Further, $\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{w_{2},c}\neq\emptyset$ and
$\mathcal{L}_{w_{1},c}\cap\mathcal{L}_{v_{2},c}\neq\emptyset$, so
$\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{w_{2},c}$ and
$\mathcal{L}_{w_{1},c}\cup\mathcal{L}_{v_{2},c}$ each mix. Note that the union
of these two sets is $\mathcal{L}$. If $\ell(P_{1})$ is odd, then
$\mathcal{L}_{v_{2},c}\cap\mathcal{L}_{w_{2},c}\neq\emptyset$, so
$\mathcal{L}$ mixes, since the cycle in $G\setminus\\{v_{2},w_{2}\\}$ is even
and thus 2-choosable. So we assume $\ell(P_{1})$ is even. Similarly, we assume
$\ell(P_{2})$ is even. Suppose that $\varphi(v_{3})=c$, $\varphi(w_{2})=c$ and
$\varphi(w_{3})=\alpha$, for some $\alpha\in\\{a,b\\}$. Since $\ell(P_{1})$
and $\ell(P_{2})$ are both even, the $\alpha,c$-component containing $w_{3}$
has vertex set $\\{v_{2},v_{3},w_{2},w_{3}\\}$. Now performing an
$\alpha,c$-swap on this component yields a valid $L$-coloring
$\varphi^{\prime}$ with $\varphi^{\prime}(v_{2})=c$. Thus, $\mathcal{L}$ mixes
when $L(y)=\\{a,b\\}$.

Instead assume that $L(y)=\\{a,c\\}$ for each interior vertex $y$ of $P_{2}$.
Again $\mathcal{L}_{v_{1},c}$, $\mathcal{L}_{w_{1},c}$
$\mathcal{L}_{v_{2},b}$, and $\mathcal{L}_{w_{2},b}$ each mix. Further,
$\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{w_{1},c}\cup\mathcal{L}_{v_{2},b}\cup\mathcal{L}_{w_{2},b}$
mixes. If $\varphi\in\mathcal{L}_{v_{1},a}\setminus\mathcal{L}_{w_{1},c}$,
then an $a,c$-swap at $v_{1}$ yields some
$\varphi^{\prime}\in\mathcal{L}_{v_{1},c}$, as in Case 1, and we are done.
Similarly, if $\varphi\in\mathcal{L}_{v_{2},a}\setminus\mathcal{L}_{w_{2},b}$,
then we use an $a,b$-swap at $v_{2}$. So instead we assume that
$\varphi\in(\mathcal{L}_{v_{1},b}\cap\mathcal{L}_{v_{2},c})\setminus(\mathcal{L}_{w_{1},c}\cup\mathcal{L}_{w_{2},b})$.
But now a $b,c$-swap at $v_{1},v_{2}$ yields an $L$-coloring in the set above
that mixes. So $\mathcal{L}$ mixes.

Case 3: $\bm{\ell(P_{1})\geq\ell(P_{2})\geq\ell(P_{3})>1.}$ By symmetry, we
assume that $L(x)=\\{a,b\\}$ for all interior vertices $x$ of $P_{1}$. First
suppose that $L(y)=\\{a,b\\}$ and $L(z)=\\{a,b\\}$ for all interior vertices
$y$ of $P_{2}$ and all interior vertices $z$ of $P_{3}$. Now
$\mathcal{L}_{v_{i},c}$ and $\mathcal{L}_{w_{j},c}$ each mix, for all
$i,j\in[3]$. Further, since
$\mathcal{L}_{v_{i},c}\cap\mathcal{L}_{w_{j},c}\neq\emptyset$ for all distinct
$i,j\in[3]$, we get that $\mathcal{L}_{v_{i},c}\cup\mathcal{L}_{w_{j},c}$
mixes for all distinct $i,j\in[3]$. Applying this idea repeatedly,
$\mathcal{L}_{v_{1},c}$ mixes with $\mathcal{L}_{w_{2},c}$, which mixes with
$\mathcal{L}_{v_{3},c}$, which mixes with $\mathcal{L}_{w_{1},c}$, which mixes
with $\mathcal{L}_{v_{2},c}$. Thus, $\cup_{i\in[3]}\mathcal{L}_{v_{i},c}$
mixes. But this union is $\mathcal{L}$, so $\mathcal{L}$ mixes.

Suppose instead that $\varphi(x)=\varphi(y)=\\{a,b\\}$ for all interior
vertices $x$ of $P_{1}$ and interior vertices $y$ of $P_{2}$, but that
$\varphi(z)=\\{a,c\\}$ for all interior vertices $z$ of $P_{3}$. As above,
$\mathcal{L}_{v_{1},c}$, $\mathcal{L}_{v_{2},c}$, $\mathcal{L}_{w_{1},c}$, and
$\mathcal{L}_{w_{2},c}$ each mix. Also
$\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{w_{2},c}\neq\emptyset$ and
$\mathcal{L}_{v_{2},c}\cap\mathcal{L}_{w_{1},c}\neq\emptyset$. Finally,
$\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{w_{1},c}\neq\emptyset$, since every
cycle is colorable from every 2-assignment unless all lists are equal (and the
cycle is odd). Assume instead that $\varphi(v_{3})=\varphi(w_{3})=c$. By
symmetry, assume that $\varphi(v_{1})=b$. Now a $b,c$-swap at $v_{3}$ gives an
$L$-coloring $\varphi^{\prime}$ with $\varphi^{\prime}(v_{1})=c$ and
$\varphi^{\prime}(v_{3})=b$. Thus, $\mathcal{L}$ mixes.

Finally, assume that $\varphi(x)=\\{a,b\\}$ for all interior vertices $x$ of
$P_{1}$, that $\varphi(y)=\\{a,c\\}$ for all interior vertices $y$ of $P_{2}$,
and that $\varphi(z)=\\{b,c\\}$ for all interior vertices $z$ of $P_{3}$.
Similar to above,
$\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{w_{1},c}\cup\mathcal{L}_{v_{2},b}\cup\mathcal{L}_{w_{2},b}\cup\mathcal{L}_{v_{3},a}\cup\mathcal{L}_{w_{3},a}$
mixes. So assume that $\varphi$ is not in this set of colorings. By symmetry
(possibly swapping $P_{2}$ with $P_{3}$ and interchanging colors $a$ and $b$),
we assume that $\varphi(v_{1})=a$, $\varphi(v_{2})=c$, and $\varphi(v_{3})=b$.
In order to complete this coloring, the lengths of $P_{1}$, $P_{2}$, and
$P_{3}$ must have the same parity.

Suppose that $P_{1}$, $P_{2}$, and $P_{3}$ all have even length. So
$\varphi(w_{1})=\varphi(v_{1})=a$, $\varphi(w_{2})=\varphi(v_{2})=c$, and
$\varphi(w_{3})=\varphi(v_{3})=b$. Now a $c,b$-swap at $v_{2}$ recolors all of
$P_{3}$, as well as $v_{2}$ and $w_{2}$. This gives a new $L$-coloring
$\varphi^{\prime}$ with $\varphi^{\prime}(v_{2})=\varphi^{\prime}(w_{2})=b$,
which mixes with all $L$-colorings above. Assume instead that $P_{1}$,
$P_{2}$, and $P_{3}$ all have odd length. So $\varphi(w_{1})=b$,
$\varphi(w_{2})=a$, and $\varphi(w_{3})=c$. Now a $c,b$-swap at $v_{2}$
recolors all of $P_{3}$, as well as $v_{2}$ and $w_{1}$. This gives a new
$L$-coloring $\varphi^{\prime\prime}$ with $\varphi^{\prime\prime}(v_{2})=b$
and $\varphi^{\prime\prime}(w_{1})=c$, which mixes with all $L$-colorings
above. Thus, $\mathcal{L}$ mixes. ∎

##  3 Proofs of Structural Lemmas

In this section, we prove our two structural lemmas. For convenience, we
restate them. Recall, for a plane graph $G$, that the subgraph _$G_{3}$_
††margin:  $G_{3}$ is induced by all edges incident to vertices of degree 3.
If two vertices of degree 3 are adjacent, then $G$ contains an edge $vw$ such
that $d(v)+d(w)=6$, so the next lemma clearly holds. Otherwise, the subgraph
$G_{3}$ must be bipartite.

######  Structural Lemma 1.

If $G$ is a simple plane graph with $\delta\geq 2$, then either

  * (C1)

$G$ contains an edge $vw$ with $d(v)+d(w)\leq\max\\{11,\Delta+2\\}$; or

  * (C2)

$G_{3}$ contains a bipartite barbell (possibly short); or

  * (C3)

$G_{3}$ contains a bipartite $\theta$-graph other than $K_{2,3}$.

Our proof is similar to a proof by Cohen and Havet [6] of Borodin’s result
that every simple planar graph with $\Delta\geq 9$ is $(\Delta+1)$-edge-
choosable. In fact, their proof implicitly contains an analogous structural
lemma. The main difference is that now we require either (C2) or (C3), whereas
they were satisfied with an even cycle in $G_{3}$. Since (C2) and (C3) each
contain an even cycle, our version of the structural lemma is stronger.

###### Proof.

Suppose the lemma is false, and let $G$ be a counterexample minimizing
$\|G\|$. We use discharging with initial charge $d(v)-4$ for each vertex $v$
and initial charge $\ell(f)-4$ for each face $f$. For each component of
$G_{3}$, we also use a “pot” with initial charge 0. By Euler’s formula, the
sum of these initial charges is $\sum_{v\in V(G)}(d(v)-4)+\sum_{f\in
F(G)}(\ell(f)-4)=4\|G\|-4|G|-4|F(G)|=-4(|F(G)|-\|G\|+|G|)=-8$. So to reach a
contradiction, it suffices to discharge so that each vertex, face, and pot
finishes with nonnegative charge. We use the following three discharging
rules, applied in succession.

  1. (R1)

Each $\Delta$-vertex with a 3-neighbor sends charge $1/2$ to the pot for its
component of $G_{3}$; each 3-vertex takes 1 from the pot for its component of
$G_{3}$.

  2. (R2)

Each $5^{+}$-vertex distributes its remaining charge equally, after possibly
applying (R1), among its incident faces (with multiplicity, if applicable).

  3. (R3)

Each 3-vertex that lies on a 4-cycle in $G_{3}$ takes 1/2 from each incident
$4^{+}$-face and sends it to the pot for its component of $G_{3}$.

Now we show that each vertex, face, and pot ends with charge nonnegative. Note
that $\delta\geq 3$, since $G$ has no instance of (C1). If $v$ is a 3-vertex,
then it takes charge 1 from the pot of its component, by (R1), and ends with
charge $3-4+1=0$. (Note that (R3) does not affect the final charge of $v$.) If
$v$ is a 4-vertex, then it starts and ends with charge 0. If $v$ is a
$5^{+}$-vertex, then it ends with charge 0, by (R2). Next we consider faces.
Let $f$ be a $4^{+}$-face. If $f$ is not incident to any 3-vertex, then it
starts with charge $\ell(f)-4\geq 0$ and ends with at least this much. Suppose
instead that $f$ has an incident 3-vertex $v$. Since $G$ has no instance of
(C1), every neighbor of $v$ along $f$ is a $\Delta$-vertex. Further,
$\Delta\geq 9$, since $\Delta+3>11$. Also, the number of $\Delta$-vertices
incident to $f$ is at least the number of incident 3-vertices (with
multiplicity), and each $9^{+}$-vertex gives at least $1/2$ to each incident
face (see Claim 1 below for details). So $f$ receives at least as much charge
from $\Delta$-vertices as it gives to 3-vertices. Hence $f$ ends with charge
at least $\ell(f)-4\geq 0$. So all that remain to consider are 3-faces and
pots. We bound the final charge of 3-faces via the following claim.

######  Claim 1.

If a 3-face $f$ is incident to an $s$-vertex $v$ with $s\geq 5$, then $v$
sends $f$ at least $1/5$ if $s\geq 5$, at least $1/3$ if $s\geq 6$, at least
$3/7$ if $s\geq 7$, and at least $1/2$ if $s\geq 8$.

Proof. If $s\leq\Delta-1$ or $v$ has no 3-neighbor, then this is clear since
each face incident to $v$ receives at least $(s-4)/s$. Now suppose that
$s=\Delta$ and $v$ has a 3-neighbor. Since $G$ has no instance of (C1), this
implies that $s\geq 9$. Now each face incident to $s$ receives
$(s-4-1/2)/s=1-9/(2s)$; this is at least $1/2$, since $s\geq 9$. This proves
the claim.  $\diamondsuit$

Now let $f$ denote a 3-face and let $t$ denote the smallest degree of a vertex
incident to $f$. Since $f$ starts with charge $3-4=-1$, to end nonnegative it
must receive at least 1. Since $G$ has no instance of (C1), each edge $vw$ has
$d(v)+d(w)\geq 12$. If $t\leq 4$, then $f$ is also incident to two
$8^{+}$-vertices, so $f$ receives at least $0+2(1/2)=1$. If $t=5$, then $f$ is
also incident to two $7^{+}$-vertices, so $f$ receives at least
$1/5+2(3/7)>1$. And if $t=6$, then $f$ receives at least $3(1/3)=1$. Thus,
each 3-face finishes with nonnegative charge.

Finally, consider a component $H$ of $G_{3}$. Denote by $n_{3}$ and
$n_{\Delta}$ the numbers of 3-vertices and $\Delta$-vertices in $H$. Note that
each 3-vertex in $H$ has all its incident edges in $H$, so $\|H\|=3n_{3}$.
First suppose that $H$ contains at most one cycle. Now
$3n_{3}=\|H\|\leq|H|=n_{3}+n_{\Delta}$, so $2n_{3}\leq n_{\Delta}$. Thus, the
pot for $H$ ends nonnegative. Next suppose that $H$ contains at least two
distinct cycles. If $H$ contains two cycles that intersect in at most one
vertex, then $H$ contains a barbell, formed from the these two cycles and a
shortest path joining them. We are done, since (C2) holds.

Suppose instead that every pair of cycles in $H$ intersect in at least two
vertices. Now the union of any two cycles in $H$ contains a $\theta$-graph. If
$G_{3}$ contains any $\theta$-graph other than $K_{2,3}$, then we are done,
since (C3) holds. So assume it does not. Let $H^{\prime}$ denote the subgraph
of $H$ induced by edges on cycles in $G_{3}$. Note that $H^{\prime}$ is
$K_{2,t}$ for some integer $t$. To see this, consider an ear decomposition of
$H^{\prime}$, starting with an arbitrary cycle. If the cycle is not a 4-cycle
or the first ear does not have length 2, then the cycle plus the first ear is
a $\theta$-graph other than $K_{2,3}$, as desired. So every cycle in
$H^{\prime}$ must be a 4-cycle (since it can start an ear decomposition), and
every ear must have length 2 (and so must connect two vertices in the same
part). Further, all ears must connect the same two vertices or we get a
$\theta$-graph other than $K_{2,3}$. This proves that $H^{\prime}=K_{2,t}$.

To prove that the pot for $H$ ends with nonnegative charge, we show that we
can direct the edges of $H$ so that each of its $\Delta$-vertices has
outdegree 1, each of its 3-vertices has indegree at least 1 and each of its
3-vertices has indegree 2 if it is either not in $H^{\prime}$ or not on a
$4^{+}$-face. Given such an orientation, we are done, since we can view each
3-vertex as receiving charge $1/2$ from each of its inneighbors, and from its
incident $4^{+}$-face, if it has one.

For each edge not in $H^{\prime}$, we simply direct it toward $H^{\prime}$.
This ensures that each 3-vertex has indegree at least 1 and that each 3-vertex
not in $H^{\prime}$ has indegree 2. First suppose that $H^{\prime}$ contains
at least three $\Delta$-vertices. In fact, it contains exactly three, and
$H^{\prime}=K_{2,3}$. In this case, at least one 3-vertex $x$ in $H^{\prime}$
will lie on a $4^{+}$-face. We direct an edge from one $\Delta$-vertex to $x$,
and direct edges from the other two $\Delta$-vertices to the remaining
3-vertex in $H^{\prime}$.

So assume instead that $H^{\prime}$ contains exactly two $\Delta$-vertices;
denote these by $x$ and $y$. Consider a vertex $z$ in $H^{\prime}$ that is
adjacent to $x$ and $y$. Since $z$ has only one incident edge besides $xz$ and
$yz$, the path $xzy$ must be part of the boundary of exactly one face incident
with $z$. If that face does not contain edge $xy$, then it is a $4^{+}$-face.
Since $G$ is simple, at most two verices $z$ can lie on a 3-face, $xyz$. We
direct an edge from $x$ to one of these two vertices and direct an edge from
$y$ to the other. This completes the desired orientation of $H^{\prime}$,
which shows that the pot for $H$ ends with nonnegative charge. It also
finishes the proof of the lemma. ∎

Recall, for a plane graph $G$, that the subgraph _$G_{2}$_ ††margin:  $G_{2}$
is induced by all edges incident to vertices of degree 2 that lie on at least
one 3-face. If two such vertices are adjacent, then $G$ contains an edge $vw$
with $d(v)+d(w)=4$, so the lemma below is clearly true. Otherwise, $G_{2}$ is
bipartite (with all vertices of degree 2 in one part). As a result, we call
every cycle in $G_{2}$ a _2-alternating cycle_.

######  Structural Lemma 2.

If $G$ is a simple plane graph with $\delta\geq 2$, then either

  * (C1)

$G$ contains an edge $vw$ with $d(v)+d(w)\leq 16$; or

  * (C2)

$G_{2}$ contains a bipartite barbell (possibly short); or

  * (C3)

$G_{2}$ contains either $K_{2,4}$ or a bipartite $\theta$-graph other than
$K_{2,3}$.

###### Proof.

Assume the lemma is false, and let $G$ be a counterexample minimizing $\|G\|$.
Note that $d(v)+d(w)\geq 17$ for every edge $vw\in E(G)$ and that $G$ is
connected. To reach a contradiction, we use discharging with initial charge
$d(v)-4$ for each vertex $v$ and $\ell(f)-4$ for each face $f$. For each
component of $G_{2}$, we also have a “pot” with initial charge 0. Since these
initial charges sum to $-8$, it suffices to discharge so that every vertex,
face, and pot ends with nonnegative charge. We use the following five
discharging rules, applied successively.

  1. (R1)

Each $15^{+}$-vertex $v$ with a 2-neighbor gives 1 to the pot for the
component of $G_{2}$ containing $v$, and each 2-vertex takes 1 from the pot
for its component of $G_{2}$.

  2. (R2)

Each $5^{+}$-vertex $v$ splits its remaining charge equally among all incident
faces (with multiplicity, if $v$ lies on the face boundary multiple times).

  3. (R3)

Each 3-vertex takes 1/3 from each incident face (with multiplicity, if
applicable).

  4. (R4)

Each 2-vertex takes 1/3 from each incident 3-face, 2/3 from each incident
4-face with boundary that induces a 2-alternating cycle, and 1 from each other
incident $4^{+}$-face (with multiplicity, if applicable).

  5. (R5)

After applying all rules above, any positive charge at a 2-vertex is returned
to the pot for its component of $G_{2}$.

Now we show that each vertex, face, and pot finishes with nonnegative charge.
Note that each $k$-vertex, with $k\geq 5$ gives each incident face at least
$(k-4)/k$ or $(k-5)/k$, the former unless $k\geq 15$. Thus, each face $f$
receives at least $1/3$ from each incident $6^{+}$-vertex and at least $2/3$
from each incident $12^{+}$-vertex.

Each 2-vertex $v$ finishes with charge at least $2-4+1+(1/3)+(2/3)=0$, since
$G$ is simple, which implies that $v$ lies on at least one $4^{+}$-face. Each
3-vertex $v$ finishes with charge $3-4+3(1/3)=0$. Each 4-vertex finishes with
charge $4-4=0$. Each $5^{+}$-vertex finishes with charge 0, by (R2).

Let $f$ be a $4^{+}$-face. Let $s$ denote the smallest degree of any vertex
incident to $f$. If $s\geq 4$, then $f$ starts nonnegative, receives charge
from incident vertices, and does not give away charge, so ends positive. If
$s=3$, then each incident 3-vertex is preceded along $f$ by a
$14^{+}$-neighbor (in some consistent direction); each such vertex pair gives
$f$ a net charge of at least $2/3-1/3$; so $f$ ends with positive charge. Now
assume that $s=2$. If $f$ is a 4-face and its boundary is a 2-alternating
cycle, then $f$ finishes with at least $4-4+2(2/3)-2(2/3)=0$. Suppose instead
that $f$ is a 4-face, but its boundary does not induce a 2-alternating cycle.
The vertices incident to $f$ include a single 2-vertex and at least two
$15^{+}$-vertices. Thus, $f$ finishes with at least $4-4+2(2/3)-1-1/3=0$.
Finally, suppose $f$ is a $5^{+}$-face. Now each incident $3^{-}$-vertex is
preceded along $f$ (in some consistent direction) by a $14^{+}$-vertex, and
the net charge given to these two vertices is at most 1/3. Thus, $f$ finishes
with at least $\ell(f)-4-\lfloor\ell(f)/2\rfloor/3\geq 5\ell(f)/6-4>0$.

Let $f$ be a 3-face, and let $s$ denote the smallest degree of any vertex
incident to $f$. If $s\geq 6$, then each incident vertex gives $f$ at least
$1/3$, so $f$ finishes with at least $3-4+3(1/3)=0$. So suppose that $s\leq
5$. Now $f$ has a single incident $5^{-}$-vertex, which receives at most $1/3$
from $f$. Each other incident vertex gives $f$ at least $2/3$, so $f$ ends
with at least $3-4+2(2/3)-1/3=0$.

Finally, we consider the pot for a component $H$ of $G_{2}$. If $H$ has at
least as many $\Delta$-vertices as 2-vertices, then the pot is nonnegative, by
(R1). So assume this is not the case. Thus, $H$ contains at least two cycles.
If two cycles in $H$ intersect in at most one vertex, then (C2) in the
statement of the lemma holds (take a minimal connected subgraph containing the
cycles). So assume that every pair of cycles in $H$ intersect in at least two
vertices. Now let $H^{\prime}$ be the union of all cycles in $H$. Since
$H^{\prime}$ is 2-connected, we consider an ear decomposition. If $H^{\prime}$
contains a cycle of any length other than 4, then we consider a $\theta$-graph
consisting of that cycle and the next ear in an ear decomposition. Now $G$
contains a $\theta$-graph other than $K_{2,3}$, so (C3) holds. So assume that
$H^{\prime}=K_{2,t}$ for some $t\geq 3$ (the analysis is similar to the
previous proof, but easier). If $t\geq 4$, then (C3) holds. So assume that
$H^{\prime}=K_{2,3}$. This implies that $H$ is formed from $K_{2,3}$ by adding
one or more pendant (even-length) paths at its $\Delta$-vertices. Denote the
vertex set of $H^{\prime}$ by $\\{x_{1},x_{2},y_{1},y_{2},y_{3}\\}$ where each
$x_{i}$ is a $\Delta$-vertex in $G$ and $d_{H^{\prime}}(x_{i})=3$ and
$d_{H}(y_{j})=2$ for all $i,j$.

We consider the number of incidences $(y_{i},f)$, where $i\in[3]$ and ($f$
ranges over all faces). Let $a_{1}$, $a_{2}$, $a_{3}$ denote the numbers of
these incidences, respectively, where $f$ is a 3-face, where $f$ is a 4-face
with boundary inducing a 2-alternating cycle, and where $f$ is another
$4^{+}$-face. If $(y_{i},f)$ is counted by $a_{1}$, $a_{2}$, or $a_{3}$, then
$f$ sends $y_{i}$ a charge of $1/3$, $2/3$, or $3/3$ (respectively), by (R4).
We claim that $a_{1}\leq a_{3}$. This implies that the total charge received
by the $y_{i}$’s from their incident faces is at least $6(2/3)=4$. So the net
charge that the $y_{i}$’s receive from their pot is at most 2, as desired.

Now we prove that $a_{1}\leq a_{3}$, as claimed. Note that each face $f$
incident to some $y_{i}$ contains as part of its boundary the path
$x_{1}y_{i}x_{2}$. If this boundary contains $x_{1}x_{2}$, then $f$ is a
3-face; otherwise, $f$ is a $4^{+}$-face. Since $G$ is simple, at most two of
these incident faces are 3-faces; that is, $a_{1}\leq 2$. If $a_{1}=0$, then
we are done. So assume that $x_{1}x_{2}\in E(G)$. Consider the three 4-faces
of $H^{\prime}$, with boundaries $x_{1}y_{i}x_{2}y_{j}$ for each pair of
distinct $i,j\in[3]$. The edge $x_{1}x_{2}$ lies inside one of these, forming
the two 3-cycles $x_{1}y_{i}x_{2}$ and $x_{1}y_{j}x_{2}$. If both of these
3-cycles are 3-faces of $G$, then the remaining edges incident to $x_{1}$ and
$x_{2}$ must each lie inside another of these 4-cycles. So two of the
$y_{i}$’s each lie on some $4^{+}$-face that does not induce a 2-alternating
cycle. This is the case that $a_{1}=2$ and $a_{3}\geq 2$. Suppose instead that
$a_{1}=1$. Now again, the remaining edges incident to $x_{1}$ and $x_{2}$ must
appear inside one of these 4-cycles, which implies that $a_{3}\geq 1$. So in
every case we have $a_{1}\leq a_{3}$, as desired. This proves the claim and
finishes the lemma. ∎

## Appendix: Proof of Lemma 1

A key ingredient in the proofs of both Main Theorem 1 and Main Theorem 2 is
Lemma 1, which was proved in [7]. However, since that manuscript is not yet
published (or refereed), for completeness we include a proof below. This proof
is essentially copied from [7]. First, we restate Lemma 1.

######  Lemma 1.

Fix a graph $G$ and a function $f:V(G)\to\mathbb{Z}^{+}$. Let $H$ be an
induced subgraph of $G$ such that $G-H$ is $f$-swappable. Let
$f^{\prime}(x):=f(x)-(d_{G}(x)-d_{H}(x))$ for all $x\in V(H)$. If
$f^{\prime}(x)\geq d_{H}(x)$ for all $x\in V(H)$ and $H$ is both
$f^{\prime}$-choosable and $f^{\prime}$-swappable, then $G$ is $f$-swappable.

######  Definition 16.

For a graph $G$ and a list assignment $L$ for $G$, an $L$-coloring $\varphi$
of $G$ is _$\alpha,\beta$ -versatile at $w$_ if
$\varphi(w)\in\\{\alpha,\beta\\}$ and an $\alpha,\beta$-swap at $w$ is
$L$-valid for $\varphi$.

######  Lemma 17.

Fix a graph $G$, a connected subgraph $H$, and a list assignment $L$ for $G$.
Let $\varphi^{\prime}$ be an $L$-coloring for $G-H$ that is
$\alpha,\beta$-versatile at a vertex $w$. If $|L(v)|\geq d_{G}(v)$ for all
$v\in V(H)$, and $H$ is not a Gallai tree, then there exists an $L$-coloring
$\varphi$ of $G$ that extends $\varphi^{\prime}$ such that $\varphi$ is
$\alpha,\beta$-versatile at $w$. Further, there exists such an $L$-coloring
$\varphi$ with the property that each $\alpha,\beta$-component of $\varphi$
contains the vertex set of at most one $\alpha,\beta$-component of
$\varphi^{\prime}$.

###### Proof.

Since $H$ is not a Gallai tree, it contains an induced even cycle, $C$, with
at most one chord. We first show how to extend $\varphi^{\prime}$ to $G-C$,
and then how to extend it to all of $G$.

A key step is to show that if $|V(H)|\geq 2$ and $x\in V(H)$, then there
exists an $L$-coloring $\varphi$ of $G-(H-x)$ that extends $\varphi^{\prime}$
to $x$ and that is $\alpha,\beta$-versatile at $w$. Suppose that $|V(H)|\geq
2$ and fix $x\in V(H)$. When choosing a color for $x$ (for brevity, we denote
it by $\varphi^{\prime}(x)$), to ensure that the resulting extension of
$\varphi^{\prime}$ is an $L$-coloring that is $\alpha,\beta$-versatile at $w$,
we need to check the following properties: (a)
$\varphi^{\prime}(x)\neq\varphi^{\prime}(y)$ for all $y\in N(x)\setminus
V(H)$, (b) if $\varphi^{\prime}(x)\in\\{\alpha,\beta\\}$ and $x$ has a
neighbor $y\notin H$ with $\varphi^{\prime}(y)\in\\{\alpha,\beta\\}$, then
$\\{\alpha,\beta\\}\subseteq L(x)$, and (c) if
$\varphi^{\prime}(x)\in\\{\alpha,\beta\\}$, then $x$ has at most one neighbor
$y\notin H$ with $\varphi^{\prime}(y)\in\\{\alpha,\beta\\}$. Now (a) ensures
the extension is a proper $L$-coloring; (b) ensures that an
$\alpha,\beta$-swap at $w$ will not create a problem at $x$; and (c) ensures
that each $\alpha,\beta$-component of $\varphi$ contains at most one
$\alpha,\beta$-component of $\varphi^{\prime}$ and that an $\alpha,\beta$-swap
at $x$ will not create a problem at $y$.

We form a list assignment $L^{\prime}(x)$ from $L(x)$ by first removing each
color that is used by $\varphi^{\prime}$ on a neighbor of $x$. Further, if
$\alpha$ is used on a neighbor of $x$ and $\alpha\notin L(x)$, then we remove
$\beta$ from $L(x)$. Similarly, if $\alpha$ is used on two neighbors of $x$,
then we remove $\beta$ from $L(x)$, regardless of whether or not $\alpha\in
L(x)$. We also remove $\alpha$ from $L(x)$ if either of these situations
occurs, but with $\beta$ and $\alpha$ interchanged. Since $|L(x)|\geq
d_{G}(x)$, we must have $|L^{\prime}(x)|\geq d_{H}(x)\geq 1$, because $H$ is
connected and $|V(H)|\geq 2$. To extend $\varphi^{\prime}$ to $x$, we simply
choose any color in $L^{\prime}(x)$. This completes the key step, started in
the previous paragraph. To extend $\varphi^{\prime}$ to $G-C$, we repeatedly
apply the key step, coloring vertices in order of non-increasing distance from
$C$. Now we show how to extend $\varphi^{\prime}$ to $C$.

First suppose that $C$ has no chord. For each $v\in V(C)$, form
$L^{\prime}(v)$ as in the previous paragraph. Again, $|L^{\prime}(v)|\geq 2$
for all $v\in V(C)$. First suppose there exists $\gamma$ and $x,y\in V(C)$
such that $\gamma\notin\\{\alpha,\beta\\}$ and $xy\in E(C)$ and $\gamma\in
L^{\prime}(x)\setminus L^{\prime}(y)$. Now we color $x$ with $\gamma$ and
proceed around $C$ finishing with $y$. This process succeeds because each time
we color another vertex $z_{1}$ we reduce the number of allowable colors on
its uncolored neighbor $z_{2}$ by at most one (even if we completely repeat
the process of removing colors as in the previous paragraph, treating $z_{1}$
as though it is outside $H$). We can finish at $y$ because the color on $x$
does not restrict our choice of color for $y$. Suppose instead that there
exists $\gamma\notin\\{\alpha,\beta\\}$ such that $\gamma\in L^{\prime}(v)$
for all $v\in C$. Now we use $\gamma$ on one maximum independent set in $C$
and color each remaining vertex $v$ from $L^{\prime}(v)\setminus\\{\gamma\\}$.
Finally, suppose that $L^{\prime}(v)=\\{\alpha,\beta\\}$ for each $v\in V(C)$.
Now we alternate $\alpha$ and $\beta$ around $C$. In each case, it is easy to
check that the resulting coloring $\varphi$ is $\alpha,\beta$-versatile at
$w$.

Now suppose that $C$ has a chord. Let $x$ denote one endpoint of the chord and
let $y$ and $z$ denote the neighbors of $x$ on $C$, besides the other endpoint
of the chord. Form $L^{\prime}(v)$ for each $v\in V(C)$, as above; again
$|L^{\prime}(v)|\geq d_{H}(v)$ for all $v\in V(C)$. Since $|L^{\prime}(x)|\geq
d_{H}(x)=3$, there exists $\gamma\in
L^{\prime}(x)\setminus\\{\alpha,\beta\\}$. If $\gamma\in L^{\prime}(y)\cap
L^{\prime}(z)$, then use $\gamma$ on $y$ and $z$ and color greedily toward $x$
in the remaining uncolored subgraph. So suppose instead that $\gamma\notin
L^{\prime}(y)\cap L^{\prime}(z)$; by symmetry, assume that $\gamma\notin
L^{\prime}(z)$. Now use $\gamma$ on $x$, then color the remaining uncolored
subgraph greedily in order of non-increasing distance from $z$. Again, we can
finish at $z$ because using $\gamma$ on $x$ does not restrict the choice of
color for $z$. ∎

Now we prove Lemma 1. As mentioned above, the proof mirrors that of Lemma 6,
but now Lemma 17 ensures that some extension to $H$ is versatile for the next
Kempe swap in $G-H$.

###### Proof of Lemma 1..

Fix $G$, $H$, $f$, and $f^{\prime}$ that satisfy the hypotheses of Lemma 1.
Assume that $H$ is $f^{\prime}$-choosable and $f^{\prime}$-swappable. If
$f^{\prime}(w)>d_{H}(w)$ for some $w\in V(H)$, then the proof is nearly the
same as that of Corollary 7. We delete the vertices of $H$ in order of non-
decreasing distance from $w$. Finally, we can handle all of $G-H$ at once
because, by hypothesis, $G-H$ is $f$-swappable. So instead we assume that
$f^{\prime}(x)=d_{H}(x)$ for all $x\in V(H)$. By assumption, $H$ is
$f^{\prime}$-choosable; this implies that $H$ is not a Gallai tree (since all
Gallai trees fail to be degree-choosable, as is easily shown by induction on
the number of blocks). So now we will be able to apply Lemma 17 to $H$.

Let $L$ be an $f$-assignment for $G$. Let $G^{\prime}:=G-H$. By assumption,
$G^{\prime}$ is $L$-swappable. Let $\varphi_{0}$ and $\varphi$ be two
$L$-colorings of $G$, and let $\varphi_{0}^{\prime}$ and $\varphi^{\prime}$
denote their restrictions to $G^{\prime}$. Since $G^{\prime}$ is
$L$-swappable, there exists a sequence
$\varphi_{0}^{\prime},\varphi_{1}^{\prime},\ldots,\varphi_{k}^{\prime}$ of
$L$-colorings of $G^{\prime}$, with $\varphi_{k}^{\prime}=\varphi^{\prime}$,
such that every two successive $L$-colorings differ by a single $L$-valid
Kempe swap. By induction on $k$, we extend each $\varphi_{i}^{\prime}$ to an
$L$-coloring $\varphi_{i}$ of $G$ such that every two successive $L$-colorings
in the sequence $\varphi_{0},\varphi_{1},\ldots,\varphi_{k}$ are
$L$-equivalent.

The case $k=0$ is easy, as follows. Form $L^{\prime}$ from $L$ by removing,
for each $w\in H$, from $L(w)$ each color used by $\varphi_{0}^{\prime}$ on a
neighbor of $w$ in $G-H$. Note that $|L^{\prime}(w)|\geq f^{\prime}(w)$ for
all $w\in H$. So $H$ has an $L^{\prime}$-coloring, since $H$ is
$f^{\prime}$-choosable. So assume that $k\geq 1$, and fix $i$ such that $0\leq
i\leq k-1$. Suppose that $\varphi_{i+1}^{\prime}$ differs from
$\varphi_{i}^{\prime}$ by an $\alpha,\beta$-swap at a vertex $v_{i}$. By Lemma
17, there exists an $L$-coloring $\widetilde{\varphi_{i}}$ of $G$, such that
the restriction of $\widetilde{\varphi_{i}}$ to $G^{\prime}$ is
$\varphi^{\prime}_{i}$ and an $\alpha,\beta$-swap at $v_{i}$ is $L$-valid in
$\widetilde{\varphi_{i}}$. Furthermore, the restriction of this new coloring
(after performing the $\alpha,\beta$-swap at $v_{i}$) is
$\varphi_{i+1}^{\prime}$. It now suffices to show that $\varphi_{i}$ and
$\widetilde{\varphi_{i}}$ are $L$-equivalent. We do this by a sequence of
Kempe swaps that recolors $H$ but never changes the colors on $V(G-H)$.

For each $v\in V(G-H)$, remove $\varphi^{\prime}_{i}(v)$ from $L(w)$ for each
$w\in N(v)\cap V(H)$; denote the resulting list assignment on $H$ by $L_{H}$.
Note that $|L_{H}(x)|\geq f^{\prime}(x)\geq d_{H}(x)$ for all $x\in V(H)$. If
$|L_{H}(x)|>f^{\prime}(x)$ for some $x$, then $H$ is $L_{H}$-swappable by
Corollary 7, since $|L_{H}(y)|\geq f^{\prime}(y)\geq d_{H}(y)$ for all $y\in
H$. So assume $|L_{H}(y)|=f^{\prime}(y)$ for all $y\in H$. Since $H$ is
$f^{\prime}$-swappable, the restrictions of $\varphi_{i}$ and
$\widetilde{\varphi_{i}}$ to $H$ (which are both $L_{H}$-colorings) are
$L_{H}$-equivalent. Consider a sequence of Kempe swaps that witnesses this.
Note that performing the same Kempe swaps in $G$ transforms $\varphi_{i}$ to
$\widetilde{\varphi_{i}}$ (this is because for each edge $vw$ with $v\in V(H)$
and $w\notin V(H)$, we have $\varphi^{\prime}_{i}(w)\notin L_{H}(v)$). Now
performing an $\alpha,\beta$-swap at $v_{i}$ in $\widetilde{\varphi_{i}}$
yields an $L$-coloring of $G$ that restricts to $\varphi^{\prime}_{i+1}$ on
$H$; we denote this $L$-coloring of $G$ by $\varphi_{i+1}$.

The previous two paragraphs show that we can use $L$-valid Kempe swaps to
transform $\varphi_{0}$ into an $L$-coloring $\widetilde{\varphi}$ that agrees
with $\varphi$ on $G-H$. Finally, we transform $\widetilde{\varphi}$ to
$\varphi$. This is possible precisely because $H$ is $f^{\prime}$-swappable. ∎

## Acknowledgment

Thanks to Reem Mahmoud and two referees for helpful feedback on earlier
versions of this paper.

## References

  * [1] A. S. Asratian and C. J. Casselgren.  Solution of Vizing’s problem on interchanges for the case of graphs with maximum degree 4 and related results.  J. Graph Theory, 82(4):350–373, 2016, arXiv:1403.5807.
  * [2] M. Bonamy.  Planar graphs with $\Delta\geq 8$ are $(\Delta+1)$-edge-choosable.  SIAM J. Discrete Math., 29(3):1735--1763, 2015, arXiv:1303.4025.
  * [3] M. Bonamy, N. Bousquet, C. Feghali, and M. Johnson.  On a conjecture of Mohar concerning Kempe equivalence of regular graphs.  J. Combin. Theory Ser. B, 135:179--199, 2019, arXiv:1510.06964.
  * [4] O. V. Borodin.  A generalization of Kotzig’s theorem and prescribed edge coloring of planar graphs.  Mat. Zametki, 48(6):22--28, 160, 1990.  doi:10.1007/BF01240258.
  * [5] O. V. Borodin, A. V. Kostochka, and D. R. Woodall.  List edge and list total colourings of multigraphs.  J. Combin. Theory Ser. B, 71(2):184--204, 1997.  doi:10.1006/jctb.1997.1780.
  * [6] N. Cohen and F. Havet.  Planar graphs with maximum degree $\Delta\geq 9$ are $(\Delta+1)$-edge-choosable---a short proof.  Discrete Math., 310(21):3049--3051, 2010.  doi:10.1016/j.disc.2010.07.004.
  * [7] D. W. Cranston and R. Mahmoud.  Kempe equivalent list colorings.  December 2021, arXiv:2112.07439.
  * [8] P. Erdős, A. L. Rubin, and H. Taylor.  Choosability in graphs.  In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pages 125--157. Utilitas Math., Winnipeg, Man., 1980.
  * [9] C. Feghali.  Kempe equivalence of 4-critical planar graphs.  January 2021, arXiv:2101.04065.
  * [10] C. Feghali, M. Johnson, and D. Paulusma.  Kempe equivalence of colourings of cubic graphs.  European J. Combin., 59:1--10, 2017, arXiv:1503.03430.
  * [11] T. Ito, M. Kamiński, and E. D. Demaine.  Reconfiguration of list edge-colorings in a graph.  Discrete Appl. Math., 160(15):2199--2207, 2012.  doi:10.1016/j.dam.2012.05.014.
  * [12] M. Las Vergnas and H. Meyniel.  Kempe classes and the Hadwiger conjecture.  J. Combin. Theory Ser. B, 31(1):95--104, 1981.  doi:10.1016/S0095-8956(81)80014-7.
  * [13] J. McDonald, B. Mohar, and D. Scheide.  Kempe equivalence of edge-colorings in subcubic and subquartic graphs.  J. Graph Theory, 70(2):226--239, 2012, arXiv:1005.2248.
  * [14] B. Mohar.  Kempe equivalence of colorings.  In Graph theory in Paris, Trends Math., pages 287--297. Birkhäuser, Basel, 2007.  doi:10.1007/978-3-7643-7400-6_22.