# Strengthening a theorem of Meyniel

Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand-Duchesne, Théo Pierron

► To cite this version:

Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand-Duchesne, Théo Pierron. Strengthening a theorem of Meyniel. SIAM Journal on Discrete Mathematics, 2023, 37 (2), 10.1137/22M1474394. hal-04156967

HAL Id: hal-04156967

https://hal.science/hal-04156967

Submitted on 10 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Strengthening a theorem of Meyniel

Quentin Deschamps* Carl Feghali† František Kardoš‡

Clément Legrand-Duchesne§ Théo Pierron*

July 10, 2023

**Abstract**

For an integer $k \ge 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $\alpha$ and $\beta$ whenever the coloring $\beta$ can be obtained from $\alpha$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$.

# 1 Introduction

Let $k$ be a positive integer, and let $G$ be a graph. A *Kempe chain* in colors $\{a, b\}$ is a maximal connected subgraph $B$ of $G$ such that every vertex of $B$ has color $a$ or $b$. By swapping the colors $a$ and $b$ on $B$, a new coloring is obtained. This operation is called a *K-change*. Let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $\alpha$ and $\beta$ whenever the coloring $\beta$ can be obtained from $\alpha$ by a single K-change.

A graph $G$ is *d-degenerate* if every subgraph of $G$ contains a vertex of degree at most $d$. Las Vergnas and Meyniel [1] proved the following result.

**Theorem 1.1.** If $G$ is $d$-degenerate and $k > d$ is an integer, then $\mathcal{K}_k(G)$ is connected.

Meyniel [2] strengthened this result for planar graphs by proving

**Theorem 1.2.** If $G$ is a planar graph, then $\mathcal{K}_5(G)$ is connected.

<footnote>*Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France.</footnote>

<footnote>†Univ. Lyon, EnsL, UCBL, CNRS, LIP, F-69342, Lyon Cedex 07, France.</footnote>

<footnote>‡Faculty of Mathematics, Physics, and Informatics, Comenius University, Bratislava, Slovakia.</footnote>

<footnote>§LaBRI, CNRS, Université de Bordeaux, Bordeaux, France.</footnote>
Here, the number 5 of colors cannot be replaced by 4 [3].

The proof of Theorem 1.1 implies that $\mathcal{K}_k(G)$ has diameter $O(d^{|V(G)|})$. Similarly, the proof of Theorem 1.2 implies that $\mathcal{K}_5(G)$ has diameter $O(5^{|V(G)|})$. Bonamy, Bousquet, Feghali and Johnson [4] conjectured that the former can be significantly improved.

**Conjecture 1.3.** If $G = (V, E)$ is $d$-degenerate and $k > d$ is an integer, then $\mathcal{K}_k(G)$ has diameter $O(|V|^2)$.

For $k > d + 1$ in Conjecture 1.3, a result of Bousquet and Heinrich [5] regarding the reconfiguration graph for colorings of graphs with bounded degeneracy implies the following

**Theorem 1.4.** If $G = (V, E)$ is $d$-degenerate and $k > d + 1$ is an integer, then $\mathcal{K}_k(G)$ has diameter $O(|V|^{d+1})$.

The case $k = d + 1$ in Conjecture 1.3 seems much more challenging. It was only until very recently that Bonamy, Delecroix and Legrand-Duschene [6] addressed this case for some proper subclasses of degenerate graphs such as graphs with bounded treewidth, graphs with bounded maximum average degree and $(\Delta - 1)$-degenerate graphs, where $\Delta$ denotes the maximum degree.

The object of this paper is to break the $k > d + 1$ (in fact, $k = d + 1$) barrier for the class of planar graphs, by proving the following strengthening of Theorem 1.2.

**Theorem 1.5.** If $G$ is a planar graph, then $\mathcal{K}_5(G)$ has diameter at most a polynomial in the number of vertices of $G$.

The proof of Theorem 1.5 is based on a proof method introduced in [7] and some ideas from [8], but of course has many of its own features. We also note that the proof can be adapted for a larger number of colors.

The paper is organized as follows. In Section 2, we analyze a proof from [9] to get an essential estimate (Proposition 2.2) that we use in Section 3 to prove Theorem 1.5.

# 2 The case of 3-colorable planar graphs

In [9], Mohar has proved the following theorem.

**Theorem 2.1.** Let $G$ be a 3-colorable planar graph. Then $\mathcal{K}_4(G)$ is connected.

In this section we show, by making a few simple observations, that the proof of Theorem 2.1 in fact establishes the following stronger fact that is crucial to our main theorem.

**Proposition 2.2.** Let $G$ be a 3-colorable planar graph on $n$ vertices. Then for every 4-colorings $\alpha$ and $\beta$ of $G$, there exists a sequence of $K$-changes from $\alpha$ to $\beta$ that changes the color of each vertex $O(n^2)$ times.
In particular, note that Proposition 2.2 implies that $\mathcal{K}_4(G)$ has diameter $O(n^3)$ when $G$ is a 3-colorable planar graph on $n$ vertices. The rest of this section is devoted to the proof of Proposition 2.2. We basically follow the same steps as the proof of Theorem 2.1, except that we add some complexity estimates to:

• a result of Fisk [10] that handles the case of 3-colorable planar triangulations, and

• a reduction to the (preceding) case as done by Mohar [9].

**Analysing the result of Fisk.**

We consider the theorem of Fisk [10] stated below.

**Theorem 2.3.** Let $G$ be a 3-colorable triangulation of the plane. Then $\mathcal{K}_4(G)$ is connected.

We show that the proof of Theorem 2.3, word for word, gives us the following estimate.

**Lemma 2.4.** Let $G$ be a 3-colorable triangulation of the plane on $n$ vertices. Then for every 4-colorings $\alpha$ and $\beta$ of $G$, there exists a sequence of $K$-changes from $\alpha$ to $\beta$ that changes the color of each vertex $O(n^2)$ times.

Let $f$ be a 4-coloring of a triangulation $G$ of the plane, and let $e = xy$ be an edge of $G$. We denote by $f(e) = \{f(x), f(y)\}$ the color of $e$ under $f$. If $xyz$ and $xyw$ are the two triangles containing an edge $xy$, we say that $xy$ is singular under $f$ if $f(w) = f(z)$.

To prove Lemma 2.4, we require the following key structural lemma extracted from the proof of Theorem 2.3. Note that, for a triangulation $G$ of the plane, if $G$ has a 3-coloring, then this coloring is unique up to permutations of colors. Moreover, a 4-coloring of $G$ is a 3-coloring if and only if all edges are singular.

**Lemma 2.5.** Let $G$ be a 3-colorable triangulation of the plane, and let $f$ be a 4-coloring of $G$. Then every monochromatic set of non-singular edges of $G$ contains a cycle that bounds some region of the plane.

Using this lemma, we can conclude the proof of Lemma 2.4.

*Proof of Lemma 2.4.* We shall show, by exhibiting at most $n \cdot |E(G)|$ K-changes, that any 4-coloring of $G$ is K-equivalent to the (unique) 3-coloring of $G$, which will prove the lemma. To do so, given a 4-coloring $f$ of $G$, we show how to obtain, via at most $n$ K-changes, a new coloring $g$ that is $K$-equivalent to $f$ and with more singular edges. As every edge in the 3-coloring of $G$ is singular, by iterating this argument at most $|E(G)|$ times the result will follow.

Let $e$ be a non-singular edge of $G$. By Lemma 2.5, there is a cycle in $G$ whose edges have the same color as $e$ and bounding some region $D$ of the plane. By interchanging the two colors in $\{1, 2, 3, 4\} \setminus f(e)$ in the interior of $D$, we obtain a new coloring $g$ with more singular edges than $f$ (singular edges in the interior of $D$ stay singular, while the edges of the cycle on the boundary of $D$ change from non-singular to singular). $\square$
**Reduction to the triangulation case.**

We first restate Proposition 4.3 from Mohar [9] except that we add some observations
about the number of vertices of the resulting triangulation and the number of K-changes
involved – these directly follow from Mohar’s proof.

**Proposition 2.6.** Let $G$ be a planar graph with a facial cycle $C$ and two 4-colorings $c_1, c_2$. Then there exist a graph $H$ formed from $G$ by adding a near-triangulation of size $O(|C|)$ inside $C$ and two 4-colorings $c'_1, c'_2$ of $H$ such that $c'_1|_{V(G)}$ and $c'_2|_{V(G)}$ are obtained from $c_1, c_2$ using at most $O(1)$ K-changes. Moreover, if the restriction of $c_1$ to $C$ is a 3-coloring, then $c'_1$ is a 3-coloring of $H$ that coincides with $c_1$ on $V(G)$.

We may now prove Proposition 2.2.

*Proof of Proposition 2.2.* The proof follows the same steps as Theorem 4.4 in [9]. We apply Proposition 2.6 to each face of $G$ (instead of Proposition 4.3 from [9]). We thus made $O(n)$ K-changes, and the resulting triangulation $T$ has $O(n)$ vertices. We then apply Lemma 2.4 (instead of Theorem 4.1 from [9]) to obtain a sequence of K-changes between the two colorings of $T$ that changes the color of each vertex $O(n^2)$ times. $\square$

# 3 Main Theorem

In this section we prove Theorem 1.5. Thanks to the celebrated Four Colour Theorem [11, 12], it suffices to prove the following result.

**Theorem 3.1.** Let $G$ be a plane graph with $n$ vertices. For every 5-coloring $\alpha$ of $G$ and every 4-coloring $\beta$ of $G$, there is a sequence of K-changes from $\alpha$ to $\beta$ where each vertex is recolored polynomially many times.

In the remainder of this section, we prove Theorem 3.1. Let us briefly sketch the details of the approach. The proof proceeds by induction on the number of vertices. Our aim is to describe a sequence of K-changes from $\alpha$ to $\beta$ such that each vertex is recolored at most $f(n)$ times, where $f$ will satisfy a recurrence relation given at the end of the section. To establish this, we roughly adopt the following strategy:

1. We find a 'large' independent set $I$ that is monochromatic in both $\alpha$ and $\beta$ and that contains vertices of degree at most 6 in $G$ (that $I$ is 'large' will enable us to show that $f$ is a polynomial function).

2. We introduce an operation at a vertex that we call collapsing, which when applied to each vertex of $I$ gives a new graph $H$ where the degree of each vertex of $I$ is at most 4 in $H$ and such that $F = H - I$ is planar. We use these to show that any sequence of K-changes in $F$ extends to a sequence of K-changes in $H$ and, in turn, in $G$.

3. We apply induction to find a sequence of K-changes in $F$ from any 5-coloring of $F$ to a 4-coloring of $F$ avoiding the color $\alpha(I)$. Applying Step 2, this sequence extends to a sequence in $G$ ending at a 5-coloring, where color 5 may appear only on $I$.
4. By definition, $I \subset B$ for some color class $B$ of $\beta$; so we can recolor each vertex of $B$ to color 5. Finally, noting that $G - B$ is a 3-colorable planar graph, we then apply Proposition 2.2 to recolor the remaining vertices in $G - B$ to their color in $\beta$.

In the rest of this section, we give the details and conclude with a small analysis of the maximum number of times a vertex changes its color.

### Step 1: Constructing $I$.

We prove that the required independent set $I$ exists.

**Lemma 3.2.** There exists an independent set $I$ of $G$ such that:

* all the vertices of $I$ have degree at most 6,

* $I$ is contained in a color class of $\alpha$ and of $\beta$,

* $|I| \ge \frac{n}{140}$.

*Proof.* Let $S$ be the set of vertices of degree at most 6 in $G$. Then $|S| > n/7$ since otherwise

$$ \sum_{v \in V(G)} d(v) \ge \sum_{v \in V(G)-S} d(v) \ge 7(n - \frac{n}{7}) = 6n, $$

which contradicts Euler's formula.

For $i \in \{1, \dots, 5\}$ and $j \in \{1, \dots, 4\}$ define the set

$$ S_{i,j} = S \cap \alpha^{-1}(i) \cap \beta^{-1}(j). $$

Note that each $S_{i,j}$ satisfies all the criteria from the lemma, except maybe the last. However, by the pigeonhole principle, there exists $i$ and $j$ such that $S_{i,j}$ contains at least $|S|/(5 \times 4) \ge n/140$ vertices, which concludes the proof. □

From now on, we fix a set $I$ satisfying the hypotheses of Lemma 3.2.

### Step 2: Constructing $H$ and extending recoloring sequences.

For a subset $X$ of vertices in a graph, we denote by $N(X)$ the set of neighbors of $X$ in the graph; moreover, if $X = \{v\}$, then we write $N(v)$ instead of $N(\{v\})$.

In order to construct $H$, we want to identify vertices in $N(I)$ that are colored alike (recall that $I$ is the independent set satisfying the hypotheses of Lemma 3.2) so that vertices of $I$ end up with degree 4 and the resulting graph with $I$ excluded is planar. We show that we can modify the coloring $\alpha$ so that such identifications become possible.

Let $P$ be a plane graph. For a 5-coloring $\varphi$ of $P$ and a vertex $v$ of $V(P)$ with $d(v) = 6$, we say that $v$ is $\varphi$-good if, in $\varphi$, the vertex $v$ has three neighbors colored alike or two pairs $(a, b)$ and $(c, d)$ of neighbors colored alike that are non-overlapping, i.e. such that $P - v + ab + cd$ is planar. We say that a set of vertices $X$ is $\varphi$-good if all the vertices in $X$ are $\varphi$-good. A sequence of K-changes is said to avoid color $a$ if no vertex involved in some K-change in the sequence changes its color to $a$.
**Lemma 3.3.** Let $P$ be a plane graph, $\alpha$ a 5-coloring of $P$, and $v \in I$ such that $d(v) = 6$. There exists a sequence of at most three $K$-changes avoiding $\alpha(v)$ that transforms $\alpha$ into a 5-coloring $\beta$ of $P$ such that $v$ is $\beta$-good.

*Proof.* We can assume that $v$ is not $\alpha$-good. We present a visual proof in Figure 1, where the six neighbors of $v$ are represented by circles from left to right in the cyclic ordering around $v$ and the numbers represent their color. Since $v$ is not $\alpha$-good, the neighbors of $v$ can be colored in four possible ways up to permutation of colors (if the neighbors of $v$ use exactly three colors, then the only possibility is Case 3; if they use all four colors, then we have three cases depending on the distance, on the cyclic ordering, of the two neighbors of $v$ having their color not appearing on any other neighbor of $v$).

A bold circle represents an attempt to perform a Kempe change, a curved edge between two vertices $u$ and $w$ represents a Kempe chain containing both $u$ and $w$. Dashed arrows between two configurations represent the actual Kempe changes while solid arrows point to subcases with the same configuration but with more information on the Kempe chains. Case 1 is solved in exactly one Kempe change, so Cases 2 and 4 are solved in at most two Kempe changes, and Case 3 is solved in at most three Kempe changes. $\square$

<figure><img src="image_2.png" /><figcaption>Figure 1: The proof of Lemma 3.3</figcaption></figure>

Equipped with the lemma, we shall intuitively successively process each vertex of $I$ as follows. For each $v \in I$, we apply Lemma 3.3 to make $v$ $\alpha$-good, then we identify vertices
in $N(v)$ so that $v$ has degree at most 4 in the resulting graph $P'$, and moreover, $P' - v$ is
planar. Note that since we avoid the color of $v$ in a K-change by Lemma 3.3, the vertices
of $I$ are never recolored at any stage of the construction. We now formalize this intuition.

Let $P$ be a plane graph. Let $\varphi$ be a 5-coloring of $P$. For a vertex $v$ of $P$ of degree at most 6 such that $v$ is $\varphi$-good if $d(v) = 6$, we say that $(P', \varphi')$ is the result of collapsing $(P, v, \varphi)$ if

• in the case $1 \le d(v) \le 4$, $P' = P$ and $\varphi' = \varphi$;

• in the case $d(v) = 5$, $P'$ is the graph obtained from $P$ by identifying two neighbors $u$ and $w$ of $v$ with $\varphi(u) = \varphi(w)$ into a new vertex $z$ and $\varphi'$ is the coloring obtained from $\varphi$ by setting $\varphi'(z) = \varphi(u) = \varphi(w)$;

• in the case $d(v) = 6$, $P'$ is the graph obtained from $P$ by either

- identifying three neighbors $u, w, z$ of $v$ with $\varphi(u) = \varphi(w) = \varphi(z)$ into a new vertex $x$. In this case, $\varphi'$ is obtained from $\varphi$ by setting $\varphi'(x) = \varphi(u)$, or

- for two non-overlapping pairs $(u, w)$ and $(x, z)$ of neighbors of $v$ with $\varphi(u) = \varphi(w)$ and $\varphi(x) = \varphi(z)$, identifying $u, w$ into a new vertex $s$ and $x, z$ into a new vertex $t$, and defining $\varphi'$ by setting $\varphi'(s) = \varphi(u)$ and $\varphi'(t) = \varphi(x)$.

Since $v$ is $\varphi$-good, it should be immediate that $P'$ and $\varphi'$ are well-defined, and that $P' - \{v\}$ is planar. We now focus on showing that we can extend a given recoloring sequence of the collapsed graph to a recoloring sequence of the original graph.

**Lemma 3.4.** Let $P$ be a plane graph with a 5-coloring $\varphi$. Let $v$ be a vertex of $P$ of degree at most 6 such that $v$ is $\varphi$-good if $d(v) = 6$. Let $(P', \varphi')$ be the result of collapsing $(P, v, \varphi)$. Then every sequence of K-changes in $P' - \{v\}$ starting from $\varphi' \uparrow (V(P') \setminus \{v\})$ extends to a sequence of K-changes in $P$ starting from $\varphi$. Moreover, each vertex of $P - v$ changes its color as many times as in $P' - v$, and $v$ changes its color at most once every time one of its neighbors in $P'$ changes its color to the color of $v$.

*Proof.* Each time a neighbor $w$ of $v$ is recolored in $P' - v$, we may use the same K-change in $P'$ unless it involves the color of $v$ and there is another neighbor $u$ of $v$ of the same color as $w$. In this case, since at most 3 colors appear on $N_{P'}(v)$ (as $v$ has degree 4 in $P'$) we can precede this K-change by first recoloring $v$ to a color not appearing in its neighborhood. This shows that any sequence of K-changes in $P' - \{v\}$ extends to a sequence in $P'$. To extend the sequence to $P$, observe that we can simulate in $P$ a K-change in $P'$ at a vertex $w$ by performing a K-change at each vertex that was identified to form $w$. Clearly, each vertex of $P - v$ changes its color as many times as in $P' - v$, and $v$ changes its color at most once every time one of its neighbors in $P'$ changes its color to the color of $v$, which concludes. $\square$

We now successively apply Lemma 3.4 to each vertex of $I$ in $G$, so that every vertex of $I$ becomes $\alpha$-good. We formalise this in the following lemma.
**Lemma 3.5.** Let P be a plane graph with a 5-coloring $\varphi$. If I is an $\varphi$-monochromatic independent set of vertices of degree at most 6 in P, then there is a 5-coloring $\psi$ of P for which I is $\psi$-good and a sequence of K-changes from $\varphi$ to $\psi$ that changes the color of each vertex at most $3|I|$ times.

*Proof.* We shall prove by induction on $|V(P)|$ the stronger claim that there is such a sequence that avoids the color of I.

By Lemma 3.3, we can assume, up to at most three K-changes, that I contains a vertex $v$ of degree at most 5 or a vertex of degree 6 that is $\varphi$-good. So we can let $(P', \varphi')$ be the result of collapsing $(P, v, \varphi)$. Since $P'' = P' - \{v\}$ is planar, we can apply our induction hypothesis to $P''$ (with $I - \{v\}$ instead of I and $\varphi' \upharpoonright P''$ instead of $\varphi$) to find a sequence of K-changes in $P''$ that avoids the color of $v$ and that transforms $\varphi' \upharpoonright P''$ to some 5-coloring $\varphi''$ of $P''$ so that the following holds:

* $I - \{v\}$ is $\varphi''$-good, and

* each vertex changes its color at most $3(|I| - 1)$ times.

By Lemma 3.4, this sequence extends to a sequence in G. Moreover, $v$ does not change its color (as the sequences avoids $\alpha(v)$), and every other vertex changes its color at most $3(|I| - 1) + 3 = 3|I|$ times. This completes the proof. $\square$

**Step 3: Induction.**

By Lemma 3.5, we can assume that I is $\alpha$-good. Let $n = |V(G)|$ and $f(n)$ be the maximum number of times a vertex in G is involved in a K-change. Write $I = \{v_1, \dots, v_m\}$, set $G_1 = G$, $\psi_1 = \alpha$ and, for $i = 2, \dots, m+1$, let $H_{i-1} = G_i - \{v_1, \dots, v_{i-1}\}$ where $(G_i, \psi_i)$ is the result of collapsing $(G_{i-1}, v_{i-1}, \psi_{i-1})$. Then the final graph $H_m$ is planar. Hence, by the induction hypothesis combined with Lemma 3.2 (with $H_m$ in place of G), there is a sequence of K-changes from $\psi_{m+1} \upharpoonright V(H_m)$ to some 4-coloring $\gamma'$ of $H_m$ on colors $\{1, \dots, 5\} \setminus \alpha(I)$ where each vertex changes its color at most $f(n - |I|)$ times. By successively applying Lemma 3.4 to $H_m$ etc. up until $H_1$ this same sequence extends to a sequence in G from $\alpha$ to some 5-coloring $\psi$ of G where $\psi \upharpoonright (G - I)$ uses only colors $\{1, \dots, 4\}$. Now, recalling Step 4 verbatim, by definition, $I \subset B$ for some color class B of $\beta$; so we can recolor each vertex of B to color 5. Finally, noting that $G - B$ is a 3-colorable planar graph, we then apply Proposition 2.2 to recolor the remaining vertices in $G - B$ to their color in $\beta$.

**Complexity analysis.**

By Lemma 3.5, the color of each vertex is changed at most $3|I|$ times in order to reach a 5-coloring $\psi$ in which I is $\psi$-good. During the induction step, by Lemma 3.4, the color of each vertex in I is changed at most $4f(n - |I|)$ times, while the color of the other vertices changes at most $f(n - |I|)$ times. By Proposition 2.2, the final step requires $O(n^2)$ changes of color per vertex. We deduce that $f(n)$ satisfies the recurrence

$$f(n) \le 3|I| + 4f(n - |I|) + O(n^2) \le 4f\left(n - \frac{n}{140}\right) + O(n^2).$$
The master theorem [13] then yields that each vertex changes its color $O(n^{\log_{140} (4)/139}) = O(n^{194})$ times, hence the sequence has length at most $O(n^{195})$, which concludes the proof.

# 4 Acknowledgements

We thank both reviewers for their corrections and suggestions which improved the presentation of the paper. This work was supported by Agence Nationale de la Recherche (France) under research grants ANR DIGRAPHS ANR-19-CE48-0013-01 and ANR project GrR (ANR-18-CE40-0032) and by APVV-19-0308 and VEGA 1/0743/21.

# References

[1] Michel Las Vergnas and Henri Meyniel. “Kempe classes and the Hadwiger Conjecture”. In: *Journal of Combinatorial Theory, Series B* 31.1 (1981), pp. 95–104. ISSN: 0095-8956.

[2] Henry Meyniel. “Les 5-colorations d’un graphe planaire forment une classe de commutation unique”. In: *Journal of Combinatorial Theory, Series B* 24.3 (1978), pp. 251–257. ISSN: 0095-8956.

[3] Bojan Mohar. “Akempic triangulations with 4 odd vertices”. In: *Discrete mathematics* 54.1 (1985), pp. 23–29.

[4] Marthe Bonamy, Nicolas Bousquet, Carl Feghali, and Matthew Johnson. “On a conjecture of Mohar concerning Kempe equivalence of regular graphs”. In: *Journal of Combinatorial Theory, Series B* 135 (2019), pp. 179–199.

[5] Nicolas Bousquet and Marc Heinrich. “A polynomial version of Cereceda’s conjecture”. In: *arXiv preprint arXiv:1903.05619* (2019).

[6] Marthe Bonamy, Vincent Delecroix, and Clément Legrand-Duchesne. “Kempe changes in degenerate graphs”. In: *arXiv preprint arXiv:2112.02313* (2021).

[7] Carl Feghali. “Paths between colourings of sparse graphs”. In: *European Journal of Combinatorics* 75 (2019), pp. 169–171.

[8] Eduard Eiben and Carl Feghali. “Toward Cereceda’s conjecture for planar graphs”. In: *Journal of Graph Theory* 94.2 (2020), pp. 267–277.

[9] Bojan Mohar. “Kempe Equivalence of Colorings”. In: *Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge*. Ed. by Adrian Bondy, Jean Fonlupt, Jean-Luc Fouquet, Jean-Claude Fournier, and Jorge L. Ramírez Alfonsín. Basel: Birkhäuser Basel, 2007, pp. 287–297.

[10] Steve Fisk. “Geometric coloring theory”. In: *Advances in Mathematics* 24.3 (1977), pp. 298–340. ISSN: 0001-8708.
[11] Kenneth Appel and Wolfgang Haken. "Every planar map is four colorable". In: *Con-temporary Mathematics* 98 (1989).

[12] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. "The Four-Colour Theorem". In: *Journal of Combinatorial Theory, Series B* 70.1 (1997), pp. 2–44. ISSN: 0095-8956. DOI: 10.1006/jctb.1997.1750.

[13] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*. MIT press, 2022.