<figure><img src="image_1.png" /></figure>

HAL
open science

Short and local transformations between
($\Delta + 1$)-colorings

Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, Mikaël Rabie

► To cite this version:

Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, Mikaël Rabie. Short and local transformations between ($\Delta + 1$)-colorings. 2022. hal-03663638

HAL Id: hal-03663638

https://hal.science/hal-03663638

Preprint submitted on 10 May 2022

**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.
Short and local transformations between
$(\Delta + 1)$-colorings*

Nicolas Bousquet¹, Laurent Feuilloley¹, Marc Heinrich², and Mikaël Rabie³

¹Univ. Lyon, CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69621, Lyon, France

²School of Computing, University of Leeds, UK.

³Université Paris Cité, CNRS, IRIF, F-75006, Paris, France

Abstract

Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring $\sigma$ to a target coloring $\eta$. Each pair of consecutive colorings must differ on exactly one vertex. The question becomes: is there a sequence of colorings from $\sigma$ to $\eta$?

In this paper, we focus on $(\Delta + 1)$-colorings of graphs of maximum degree $\Delta$. Feghali, Johnson and Paulusma proved that, if both colorings are non-frozen (i.e. we can change the color of a least one vertex), then a quadratic recoloring sequence always exists. We improve their result by proving that there actually exists a linear transformation.

In addition, we prove that the core of our algorithm can be performed locally. Informally, if we start from a coloring where there is a set of well-spread non-frozen vertices, then we can reach any other such coloring by recoloring only $f(\Delta)$ independent sets one after another. Moreover these independent sets can be computed efficiently in the LOCAL model of distributed computing.

# 1 Introduction

Reconfiguration problems consist in finding step-by-step transformations between two given feasible solutions of a problem, such that all intermediate states are also feasible. For a complete overview of the reconfiguration field, the reader is referred to the two recent surveys on the topic [24, 27]. In this paper, our reference problem is graph coloring.

**Graph recoloring.** All along the paper $G = (V, E)$ denotes a graph, $n := |V|$, and $k$ is a positive integer. For standard definitions and notations on graphs, we refer the reader to [17]. A (*proper*) $k$-coloring of $G$ is a function $\sigma : V(G) \to \{1, \dots, k\}$ such that, for every edge $xy \in E$, we have $\sigma(x) \neq \sigma(y)$. Throughout the paper, we only consider proper colorings, and will then omit the word “proper” for brevity. The chromatic number $\chi(G)$

<footnote>*This work was supported by ANR project GrR (ANR-18-CE40-0032)</footnote>
of a graph $G$ is the smallest $k$ such that $G$ admits a $k$-coloring. Two $k$-colorings are
adjacent if they differ on exactly one vertex. The $k$-reconfiguration graph of $G$, denoted
by $G(G, k)$, and defined for any $k \ge \chi(G)$, is the graph whose vertices are $k$-colorings
of $G$, with the adjacency relation defined above.

In this work, we will focus on the diameter of the reconfiguration graph. The *k*-recoloring diameter of a graph *G* is the diameter of *G*(*G*, *k*), if *G*(*G*, *k*) is connected, and is equal to +∞ otherwise. In other words, it is the minimum *D* for which any *k*-coloring can be transformed into any other through a sequence of at most *D* adjacent *k*-colorings. The diameter of the reconfiguration graph plays an important role, for instance in random sampling, since it provides a lower bound on the mixing time of the underlying Markov chain (and the connectivity of the reconfiguration graph ensures the ergodicity of the Markov chain<fnref n="1" />). Since proper colorings correspond to states of the anti-ferromagnetic Potts model at zero temperature, Markov chains related to graph colorings received considerable attention in statistical physics and many questions related to the ergodicity or the mixing time of these chains remain widely open (see e.g. [16, 22]).

If we consider (Δ + 2)-colorings<fnref n="2" />, the recoloring graph is indeed connected. An important conjecture in the random sampling community is that the mixing time of the (Δ + 2)-colorings of any graph is O(n log n). In other words, given any (Δ + 2)-coloring of a graph, if we perform a (lazy) random walk on the set of proper (Δ + 2)-colorings, we should sample (almost) at random a coloring after O(n log n) steps. This question is still widely open, and the best known upper bound on the number of colors to obtain a polynomial mixing time is (11/6 - ϵ)Δ [16], slightly improving a classical result of Vigoda [28]. When the number of colors is Δ + 1, one cannot expect a polynomial mixing time, since the chain is not irreducible. Indeed, if we consider for instance a clique, the (Δ + 1)-colorings are *frozen*, i.e. we cannot modify the color of any vertex. (A vertex is *non-frozen* if we can modify its color and *frozen* otherwise.)

However, Feghali, Johnson, and Paulusma [21] proved that the situation is not that bad for (Δ + 1)-colorings, since the reconfiguration graph of the (Δ + 1)-colorings of a graph is a set of isolated vertices plus a unique component containing all the other colorings, which has diameter O(n<fnref n="2" />). In other words, any non-frozen coloring can be transformed into any other with O(n<fnref n="2" />) single vertex recolorings. In addition, Bonamy, Bousquet, and Perarnau [5] proved that, if G is connected, then the proportion of frozen (Δ + 1)-colorings of G is exponentially smaller than the total number of colorings.

**1.1 Our results**

Our main result consists in proving that we can bring the quadratic term in the result
of Feghali, Johnson, and Paulusma [21] down to a linear term (by paying an additional
function of Δ).

**Theorem 1.1.** Let $G$ be a connected graph with $\Delta \ge 3$ and $\sigma, \eta$ be two non-frozen $k$-colorings of $G$ with $k \ge \Delta + 1$. Then we can transform $\sigma$ into $\eta$ with a sequence of at

<footnote n="1">¹Actually, it only gives the irreducibility of the chain. To get the ergodicity, we also need the chain to be aperiodic. For the chains associated with proper graph colorings, this property is usually straightforward.</footnote>

<footnote n="2">²All along the paper, $\Delta(G)$, or $\Delta$ when $G$ is clear from context, will denote the maximum degree of $G$.</footnote>
most $O(\Delta^{c\Delta}n)$ single vertex recolorings, where c is a constant.

In other words, we lower the upper bound on the diameter of the non-trivial component from $O(n^2)$ to $f(\Delta) \cdot n$. The existence of linear transformations between colorings received considerable attention in recent years, see e.g. [3, 2, 11, 18]. Most of the works focus on the following question: how many colors are needed in order to guarantee the existence of a linear transformation between any pair of colorings of $G$?

Most of the proofs of these results are not local since we have no control on how the set of recolored vertices is “moving” in the graph. Informally speaking, when we have a recoloring sequence that is of minimal length, if a vertex is recolored, it is either to give it its final color or because it has to be recolored since one of its neighbors wants to take its color later in the sequence. In the second case, let us call the corresponding edge a *special arc* associated to that step. So, for every step of the recoloring sequence but at most *n*, we can associate a special arc. In most of the recoloring proofs, even when the transformation is linear, we have no control on the location of the sequence of special arcs in the graph (we might have to go back and forth several times in the graph) even if all the vertices are initially non-frozen. On the contrary, our proof is local in the sense that, if we start from a coloring which is *r*-locally non-frozen, which is a coloring such that any ball of radius *r* contains a non-frozen vertex, then the length of the longest oriented path in the sequence of special arcs has bounded size. In other words, a recoloring sequence of the type “a vertex $u_1$ is recolored because a vertex $u_2$ is recolored because a vertex $u_3$ is recolored...etc...” cannot be too long. Actually, we prove an even stronger result: if both the initial and the target colorings are locally non-frozen, there exists a recoloring sequence that consists in recoloring successively a constant (in $\Delta$) number of independent sets (and then there is no long chain of special arcs and the total number of recolorings is linear). Moreover, such a recoloring sequence can be found efficiently in the LOCAL model of distributed computing$^3$.

More formally, a *recoloring (parallel) schedule of length *r* from *α* to *β* is a sequence of independent sets $S_1, \dots, S_r$ such that (i) at any step of the transformation only the vertices of $S_i$ are recolored and, (ii) at any step the coloring is proper. Note that if there is a recoloring schedule of length *r* then there is a single vertex recoloring transformation in at most *rn* steps. We say that a coloring is *r*-locally non-frozen if all the vertices are at distance at most *r* from a non-frozen vertex. We prove the following theorem.

**Theorem 1.2.** Let $G$ be a graph with $\Delta \ge 3$, $k \in \mathbb{N}$ with $k \ge \Delta + 1$. Let $\sigma, \eta$ be two $k$-colorings of $G$ which are $r$-locally non-frozen. There exists three constants $c, c', c''$ such that we can transform $\sigma$ into $\eta$ with a parallel schedule of length at most $O(k^{c\Delta} + \Delta^{c'r})$ in

* $O(\Delta^{c''} + \log^* n + k)$ rounds if $k \ge \Delta + 2$.

* $O(\Delta^{c''} + \log^2 n \cdot \log^2 \Delta + k)$ rounds otherwise.

Informally, the number of rounds we need in the LOCAL model to provide a distributed recoloring sequence can be seen as how much we need to understand the graph globally to provide a recoloring sequence. When we look into our proof, the $\log^* n$ (or

<footnote>$^3$See Section 1.2 for formal definitions on distributed algorithms.</footnote>
$\log^2 n)$ term in the number of rounds is there to compute a maximal independent set at distance $\Omega(1)$ (or a $\Delta+1$ coloring). If we are given such colorings and independent sets, the number of rounds is independent of $n$.

Note that Theorem 1.2 implies Theorem 1.1, as long as both initial and target colorings are locally non-frozen. However, we might have only a few non-frozen vertices in the graph $G$ (such colorings exist e.g. in powers of paths). In that case, we prove that we can transform a non-frozen coloring into a locally non-frozen coloring with a linear number of recoloring steps. The proof is based on a result of independent interest, which is formally stated in Section 4, that we sketch here. Given a $(\Delta+1)$-coloring, if a vertex $x$ is non-frozen, and $y$ is a vertex at distance 7 from $x$, then we can recolor the vertices of $B(x, 7)$ such that:

(i) at the end of the transformation, $x$ is still non-frozen,

(ii) no vertex of the border of $B(x, 7)$ is recolored,

(iii) $y$ is non-frozen at the end of the transformation.

Informally speaking, the result ensures that, in $(\Delta + 1)$-colorings, we can locally “dupli-cate” non-frozen vertices. Using this statement we prove, using a BFS-like structure, that we can transform the coloring into a locally non-frozen coloring (see Proposition 3.1).

Note that our proof technique is completely different from the one of Feghali et al. [21], whose proof is based on an iterative identification of vertices (and from which we can hardly expect a linear transformation).

An interesting direction for future work is to determine whether we can replace the exponential function in $\Delta$ by a polynomial function of $\Delta$. We actually have no lower bound that ensures that a dependency in $\Delta$ is necessary. In other words:

*Question 1.3.* Given $\alpha, \beta$ two non-frozen $(\Delta + 1)$-colorings, is it possible to transform $\alpha$ into $\beta$ in $O(n)$ steps independent of $\Delta$?

A first step towards this question would consist in proving that if the number of colors is large enough (compared to $\Delta$), then we can remove or reduce the dependency on $\Delta$. When $k = \Delta + 2$, a result of Bonamy and Bousquet [4] (on recolorings with the grundy coloring number) ensures that the diameter is at most $O(\Delta n)$. One can wonder if this dependency in $\Delta$ can be avoided.

Finally note that, at some steps of the proof, we can reduce the exponential depen-dency on $\Delta$ into a polynomial one by adapting a result of Bousquet and Heinrich [10] but we did not succeed to do it at every step. We thus decided to keep the proof as simple as possible.

## 1.2 LOCAL model and distributed recoloring

The LOCAL model is a classic model of distributed computing (see [26] for a survey). The model consists of a graph $G = (V, E)$ where each vertex $v \in V$ has a unique identifier. Each edge corresponds to a communication link between two vertices. Initially, each vertex only has access to its identifier and its list of neighbors. Each vertex communicates synchronously with its neighbors at each round. We say that an algorithm *runs in $\ell$ rounds*, if every vertex can run this algorithm for $\ell$ rounds and then get an output. Since
we do not impose any limit on the memory, on the information propagated along a link at each round, or the computational power of the vertices, this is equivalent to a model where every vertex knows its full neighborhood at distance at most $\ell$, and then chooses an output.

Usually, the validity of the output can be checked locally. For example, to check that a coloring is proper, a vertex just needs to check that its color output by the algorithm differs from its neighbors'. An algorithm is valid if its output is correct. In what follows, we will only consider valid algorithms.

Distributed recoloring in the LOCAL model was introduced in [7], and implicitly studied before in [25]. In [7], the authors focus on recolorings 3-colored trees, subcubic graphs and toroidal grids, and in [25], the focus is on transforming a $(\Delta + 1)$-coloring into a $\Delta$-coloring. More recently, [9] designed efficient distributed recoloring for chordal and interval graphs. A few reconfiguration problems different from coloring have been studied in the distributed setting, including vertex cover [12] and maximal independent sets [13].

Distributed recoloring in the LOCAL model is defined as follows. Each vertex $v$ is given as input its initial color $c_0$ and its target color $c_{end}$. It outputs a schedule $c_0, c_1, \dots, c_{\ell} = c_{end}$ of length $\ell$, which is the list of colors taken by $v$ all along the transformation. In one communication round, each vertex can check that the schedule is consistent by checking that at each step: (i) its color differs from its neighbors', and (ii) if its color changes at some step $i > 0$ (i.e. $c_{i-1} \neq c_i$), then the color of none of its neighbors is modified at that same step. In case we handle $r$-locally non-frozen colorings, a vertex is given as input its distance to a closest unfrozen vertex in both initial and target colorings. The input validity can be checked in one round, as each vertex just needs to check that (i) both colorings are locally proper (around its vertex), and that (ii) it is unfrozen if the integer assigned to it is 0, or it has a neighbor at a smaller distance if its distance is positive.

Theorem 1.2 directly improves some results of [7] on distributed recoloring. One problem studied in [7] consists in recoloring 3-colored graphs of maximum degree 3 with the help of an extra color. They provide an algorithm that finds a parallel schedule of length $O(\log n)$ in a polylogarithmic number of rounds in the LOCAL model. Theorem 1.2 implies that a constant length schedule can be found in $O(\log^* n)$ rounds (and it holds even we start from an arbitrary locally non-frozen 4-colorings instead of 3-colorings plus an additional color). Theorem 1.2 also directly solves two open questions from [7]:

* The first question is about the complexity of finding a schedule to recolor a $\Delta$-coloring with an extra color. Theorem 1.2 gives an algorithm that finds a parallel schedule of length $f(\Delta)$ in $O(F(\Delta) \log^* n)$ communication rounds (since these $\Delta$-colorings can be seen as non-frozen $(\Delta + 1)$-colorings).

* The second question concerns the case of 4-colored toroidal grids with an extra color. We provide an algorithm with a constant length schedule after $O(\log^* n)$ rounds.

We leave as an open problem whether a schedule can be found even faster. In particular, we conjecture that, in the case of toroidal grids, such a schedule could be found in $O(1)$ communication rounds, by using the input and target colorings as symmetry-
breaking tools. More generally, we were not able to provide a positive answer to that question:

*Question 1.4.* Does there exist a non-constant function *f* such that an algorithm computing a recoloring schedule in the LOCAL model between any pair of 28-locally non-frozen (*Δ* + 1)-colorings takes Ω(*f*(*n*)) communication rounds.

Note that a lower bound result of this flavor can be found in [13] for the problem of maximal independent set reconfiguration but we did not manage to adapt it in our setting.

## 1.3 Related work in graph recoloring

Bonsma and Cereceda [8] proved that there exists a family $\mathcal{G}$ of graphs and an integer $k$ such that, for every graph $G \in \mathcal{G}$, there exist two $k$-colorings whose distance in the $k$-reconfiguration graph is finite and super-polynomial in $n$. Cereceda conjectured that the situation is different for degenerate graphs. A graph $G$ is $d$-degenerate if any subgraph of $G$ admits a vertex of degree at most $d$. In other words, there exists an ordering $v_1, \dots, v_n$ of the vertices such that for every $i \le n$, the vertex $v_i$ has at most $d$ neighbors in $v_{i+1}, \dots, v_n$. It was shown independently in [19] and [15] that for any $d$-degenerate graph $G$ and every $k \ge d+2$, $\mathcal{G}(G,k)$ is connected. However, the (upper) bound on the $k$-recoloring diameter given by these constructive proofs is of order $c^n$ (where $c$ is a constant). Cereceda [14] conjectured that the diameter of $\mathcal{G}(G,k)$ is of order $O(n^2)$, as long as $k \ge d+2$. If correct, the quadratic function is sharp, even for paths or chordal graphs as proved in [6]. The best known bound on this conjecture is due to Bousquet and Heinrich [10], who proved that the diameter of $\mathcal{G}(G,k)$ is $n^{d+1}$. The conjecture is known to be true for a few graph classes, such as chordal graphs [6] and bounded treewidth graphs [4, 20].

# 2 Preliminaries

Let $G$ be a graph and $v$ be a vertex of $G$. We denote by $N(v)$ the set of *neighbors* of $v$, that is the set of vertices adjacent to $v$. The set $N[v]$, called the *closed neighborhood of v*, denotes the set $N(v) \cup \{v\}$. Given a set $X$, we denote by $N(X)$, the set $(\cup_{v \in X} N(v)) \setminus X$. The *distance* between $u$ and $v$ in $G$ is the length of a shortest path from $u$ to $v$ in $G$ (by convention, it is $+\infty$ if no such path exists), and it is denoted by $d(u, v)$. Let $r \in \mathbb{N}$. We denote by $B(v, r)$ the *ball* of center $v$ and radius $r$, which is the set of vertices at distance at most $r$ from $v$. A vertex $w$ belongs to the *boundary* of $B(v, r)$ if the distance between $w$ and $v$ is exactly $r$. The *interior* of a ball $B$ is the ball minus its boundary (i.e. $B(v, r-1)$ for a ball $B(v, r)$, with $r > 0$).

Let $c$ be a coloring of $G$. A vertex $v$ is *frozen* in $c$ if all the colors appear in $N[v]$. The coloring $c$ is *frozen* if all the vertices are frozen. Note that a frozen coloring is an isolated vertex of the reconfiguration graph.

Let $\alpha$ be a coloring of $G$, and $X$ be a subset of vertices. We denote by $G[X]$ the subgraph of $G$ induced by $X$, and by $\alpha_X$ the coloring $\alpha$ restricted to the vertices of $X$. We say that two colorings $\alpha$ and $\beta$ agree on $X$ if $\alpha_X = \beta_X$.
We introduce two new notions that are essential in the paper: *r*-locally non-frozen colorings and *r*-safe graphs.

**Definition 2.1.** A coloring is *r*-locally non-frozen if, for every vertex *v*, there exists a non-frozen vertex at distance at most *r* from *v*.

**Definition 2.2.** The *k*-colorings of a graph *G* are *r*-safe if, for every vertex *v*, and every *k*-coloring where *v* is non-frozen, the following holds. For any vertex *w* at distance *r* from *v*, there exists a recoloring sequence, such that: *w* is recolored, all the other recolored vertices are in the interior of *B*(*v*, *r*), and *v* is again non-frozen at the end of the sequence.

Since we only consider ($\Delta + 1$)-colorings in the paper, we will say that $G$ is *r*-safe if the ($\Delta + 1$)-colorings of $G$ are *r*-safe. Before we define yet another notion, let us make a remark.

*Remark 2.3.* Consider a non-frozen vertex *u* in a $\Delta+1$-coloring of the graph. If we change its color, then all its frozen neighbors become unfrozen.

Indeed, before the change, for any frozen neighbor *v* of *u*, all the colors appear exactly once in $N[v]$ (because we consider $\Delta + 1$ colors). Thus, after the change, the old color *c* of *u* does not appear anymore in $N[v]$, and *v* has two possible colors: its current color and *c*. Now, let us go one step further. Suppose that *v* had another neighbor *z*, not adjacent to *u*, that was also frozen at the beginning. The recoloring of *u* keeps *z* frozen, but then the recoloring of *v* with color *c* unfreeze it. By iterating this process, we get what we call a *ladder*.

**Definition 2.4.** Given an induced path *P* where the first vertex in the path is non-frozen, and all the other vertices are frozen, a ladder consists in recoloring all the vertices of *P* one by one.

Note that at the end of the sequence, the other endpoint *w* of *P* has changed color, and it is non-frozen. Moreover, for every consecutive pair of vertices $v_i v_{i+1}$ in the path, where $v_i$ appears first between *v* and *w*, the final color of $v_{i+1}$ is the initial color of $v_i$.

# 3 Outline of the proofs

The proofs of both our theorems are in two steps. The first step is slightly different, but the second step is the same for both results. The first step consists in reaching a coloring where the vertices of a fixed set *I* are all non-frozen. For Theorem 1.1 (centralized recoloring), this step corresponds to the following proposition, where we start from a non-frozen coloring.

**Proposition 3.1.** Let $G$ be a connected graph of maximum degree $\Delta \ge 3$, and let $I$ be a maximal independent set at distance $d \ge 15$ in $G$. Let $\sigma$ be a coloring of $G$ that is non-frozen. Then it is possible to transform $\sigma$ into a coloring $\mu$ where $I$ is non-frozen, with $O(n)$ single vertex recolorings.

For Theorem 1.2 (distributed recoloring), the first step corresponds to the following proposition, where we start from an *r*-locally non-frozen coloring.
**Proposition 3.2.** Let $G$ be a connected graph of maximum degree $\Delta \ge 3$, and let $I$ be a maximal independent set at distance $d \ge 15$ in $G$. Let $\sigma$ be a $r$-locally non-frozen coloring. Then it is possible to transform $\sigma$ into a coloring $\mu$ where $I$ is non-frozen, in $O(d\Delta^{4d+10} + d\log^*n + r)$ rounds, and with a schedule of length $O((r+d)d\Delta^{6d+10})$ in the LOCAL model.

Actually, the proofs of both Proposition 3.1 and 3.2 will use as an essential building block the following theorem, which is of independent interest.

**Theorem 3.3.** For every $r \ge 7$ and every graph $G$ of maximum degree $\Delta \ge 3$, $G$ is $r$-safe.

The second step, that is common to both theorems, consists in reaching a fixed coloring $\gamma$, and corresponds to the following proposition.

**Proposition 3.4.** Let $G$ be a graph with $\Delta \ge 3$ and $I$ be an independent set at distance 28. Let $r, k, k' \in \mathbb{N}$ such that $k' < k, k \ge \Delta+1$. Let $\mu, \gamma$ be two colorings, using respectively at most $k$ and $k'$ colors, that are both non-frozen on $I$. There is a recoloring schedule from $\mu$ to $\gamma$ of length at most $(k')^{O(\Delta)}$. Moreover, such a recoloring schedule can be computed in $O(\Delta)$ rounds in the LOCAL model.

Note that even if $k = \Delta + 1$, a $k$'-coloring with $k' = \Delta$ exists, by Brook's theorem. Indeed, since $\sigma$ is non-frozen and $\Delta \ge 3$, $G$ is neither a clique nor an odd cycle.

We now have all the tools to prove our two main theorems.

**Theorem 1.1.** Let $G$ be a connected graph with $\Delta \ge 3$ and $\sigma, \eta$ be two non-frozen $k$-colorings of $G$ with $k \ge \Delta + 1$. Then we can transform $\sigma$ into $\eta$ with a sequence of at most $O(\Delta^c n)$ single vertex recolorings, where $c$ is a constant.

*Proof.* By Proposition 3.1, we can transform $\sigma$ (resp. $\eta$) into a coloring $\mu$ (resp. $\mu'$) which is non-frozen on $I$ by recoloring $O(n)$ vertices in total.

Let $\gamma$ be an arbitrary $\Delta$-coloring of $G$. In order to build the recoloring sequence from $\mu$ to $\mu'$, we will build one from $\mu$ to $\gamma$, and one from $\gamma$ to $\mu'$. By Proposition 3.4, there is a recoloring schedule from $\mu$ (resp. $\mu'$) to $\gamma$ recoloring at most $\Delta^{O(\Delta)}$ independent sets. This sequence recolors at most $\Delta^{O(\Delta)}$ times each vertex, which completes the proof. $\square$

The second theorem is about local reconfiguration, and we assume that the colorings are $r$-locally non-frozen.

**Theorem 1.2.** Let $G$ be a graph with $\Delta \ge 3$, $k \in \mathbb{N}$ with $k \ge \Delta + 1$. Let $\sigma, \eta$ be two $k$-colorings of $G$ which are $r$-locally non-frozen. There exists three constants $c, c', c''$ such that we can transform $\sigma$ into $\eta$ with a parallel schedule of length at most $O(k^{c\Delta} + \Delta^{c'r})$ in

* $O(\Delta^{c''} + \log^* n + k)$ rounds if $k \ge \Delta + 2$.

* $O(\Delta^{c''} + \log^2 n \cdot \log^2 \Delta + k)$ rounds otherwise.
*Proof.* We first compute an independent set at distance $d = 28$ in a distributed manner in time $O(\Delta^{28} + \log^* n)$ rounds in the LOCAL model by [1]. Then by pluggnig the result of Proposition 3.2 with $d = 28$, we can transform $\sigma$ (resp. $\eta$) into a coloring $\mu$ (resp. $\mu'$) such that all the vertices of $I$ are non-frozen with a recoloring schedule of length $O(r\Delta^{178})$ in $O(\Delta^{122} + \log^* n + r)$ rounds.

Assume first that $k \ge \Delta + 2$. It is easy to transform $\mu$ into a coloring $\gamma$ with $k-1$ colors in one round: for every vertex that has color $\Delta + 2$, move it to a color of smaller index. Such a color must exist, and the transformation takes only one round. Now by Proposition 3.4, we can transform $\mu'$ into $\gamma$ efficiently, and finish this proof.

Now, if $k = \Delta + 1$, we first compute an arbitrary $\Delta$-coloring, in time $O(\log^2 n \log^2 \Delta)$, using the algorithm of [23], and then use Proposition 3.4 twice (between $\mu$ and $\gamma$, and between $\mu'$ and $\gamma$). $\square$

# 4 Safeness and consequences

## 4.1 Maximum degree at least 3 ensures safeness

The goal of this section is to prove the following theorem, that ensures that, in any ball with an unfrozen vertex, we can unfreeze at a vertex of its border while keeping its center unfrozen.

**Theorem 3.3.** For every $r \ge 7$ and every graph $G$ of maximum degree $\Delta \ge 3$, $G$ is $r$-safe.

Consider a graph $G$ of maximum degree $\Delta \ge 3$. Let $\sigma$ be proper $(\Delta + 1)$-coloring of $G$, and $v$ be a non-frozen vertex. Let $B = B(v, r)$. Note that if the boundary of $B$ is empty (that is, the whole graph is contained in $B(v, r-1)$) then $G$ is $r$-safe. For the rest of the section, we will assume that this is not the case.

Let $w$ be a vertex of the boundary of $B$. Our goal is to prove that there exists a recoloring sequence of the vertices of the interior of $B$ plus $w$, which recolors $w$, and such that at the end of the sequence, $v$ is still non-frozen. Moreover, we will show that this recoloring sequence recolors each vertex at most twice (and at most $2r$ vertices in total).

We will call *nice* such a recoloring sequence. The existence of a nice recoloring sequence implies Theorem 3.3. Let us first give some conditions which ensure the existence of a nice recoloring sequence.

**Lemma 4.1.** Let $P$ be a shortest path from $v$ to $w$. Assume that $P$ contains a non-frozen vertex not in $N[v]$. Then there is a nice recoloring sequence.

*Proof.* Let $z$ be the non-frozen vertex of $P$ closest to $w$. By assumption, we know that $z$ is not adjacent to $v$. Let $P'$ be the subpath from $z$ to $w$. We can recolor $w$ by recoloring a ladder along this path $P'$. Let us check that this is a nice recoloring sequence. All the vertices of $P'$, except $w$, are in the interior of $B$, because $P$ is a shortest path from the center of the ball $B$ to $w$. Moreover, after this transformation $v$ is still non-frozen since none of its neighbors were recolored. Finally, every vertex is recolored at most once. $\square$

We can extend this property to the vertices at distance 1 from the path $P$.
**Lemma 4.2.** Let $P$ be a shortest path from $v$ to $w$. Assume that there is a non-frozen vertex $z$ adjacent to $P$, such that $3 \le d(v, z) \le r-1$. Then there is a nice recoloring sequence.

*Proof.* The argument is similar to the one of Lemma 4.1. Let $z$ be a vertex satisfying the conditions of the lemma, that is the closest to $w$. Note that $z$ is in the interior of $B$, since $d(v, z) \le r-1$. Let $z'$ be the neighbor of $z$ in $P$ which is the closest to $w$, then $z'$ is at distance at least 2 from $v$, in particular, it is not a neighbor of $v$. Then, we can again recolor along a ladder that starts with $z, z'$, and then continues along $P$ towards $w$. This allows us to recolor $w$ while leaving the neighbors of $v$ and the boundary of $B$ untouched. Each vertex is recolored at most once, which implies that this is a nice recoloring sequence. $\square$

**Lemma 4.3.** Let $P = v_0, \dots, v_r$ be a shortest path from $v$ to $w$. If there is an index $2 \le i \le r-3$, such that $\sigma(v_i) \ne \sigma(v_{i+3})$, then there is a nice recoloring sequence.

*Proof.* By Lemma 4.1, we can assume that all the vertices of $P$, except for $v = v_0$ and its neighbor $v_1$, are frozen. Let us denote by $\eta$ the coloring obtained by recoloring the ladder along $P$, starting either from $v$, if $v_1$ is frozen, or $v_1$, if it is non-frozen, and ending in $w$. In $\eta$, we have recolored $w$, but now $v$ might be frozen. If $v$ is not frozen, we are done. If $v_1$ is non-frozen, then again we are done, since we can make a ladder with just $v_1$ and $v$. Thus, let us assume that both $v_1$ and $v$ are frozen in $\eta$.

Amongst the indices $2 \le i \le r-3$ such that $\sigma(v_i) \ne \sigma(v_{i+3})$, let $i$ be the minimum one. We have the following claim:

**Claim 4.4.** The vertex $v_{i+2}$ is non-frozen in the coloring $\eta$.

*Proof.* Let $c = \sigma(v_{i+3})$. Let us make a few remarks:

1. $\sigma(v_{i+2}) \ne c$, because $\sigma$ is a proper coloring,

2. $\sigma(v_{i+1}) \ne c$, because $v_{i+2}$ is frozen in $\sigma$. More generally, none of the neighbors of $v_{i+2}$ except $v_{i+3}$ has color $c$.

3. $\sigma(v_i) \ne c$, because $\sigma(v_i) \ne \sigma(v_{i+3})$ by assumption.

Now, by construction and by the properties of ladders, we have $\eta(v_{j+1}) = \sigma(v_j)$, for every vertex $v_j$ of the ladder, except $v_r = w$. Transposing the remarks above about $\sigma$ to $\eta$ we get that:

1. $\eta(v_{i+3}) \ne c$,

2. $\eta(v_{i+2}) \ne c$, and more generally, no neighbor of $v_{i+2}$ has color $c$.

3. $\eta(v_{i+1}) \ne c$.

Consequently, $c$ does not appear in the closed neighborhood of $v_{i+2}$ in $\eta$, which implies that $v_{i+2}$ is non-frozen in $\eta$, as claimed. $\square$

By Claim 4.4, $v_{i+2}$ is non-frozen in $\eta$. We can make a new ladder in $\eta$ along the path $P$ from $v_{i+2}$ to $v$. The vertex $w$ is not recolored by this ladder, and at the end $v$ is non-frozen. Since every vertex is recolored at most twice, we get a nice recoloring sequence. $\square$
We now have all the tools to prove that a nice recoloring sequence always exists. Let us assume that we do not fall in one of the previous cases. Let $P = v_0, \dots, v_r$ be a shortest path from $v$ to $w$. By Lemma 4.1, all the vertices in $P$ but the first two ones are frozen. By Lemma 4.2, all the neighbors of $P$ that are at distance at least three from $v$ are frozen. Free to rename colors, Lemma 4.3 ensures that $\sigma(v_i) = i \bmod 3$ for every $i \ge 2$. We denote by $\eta$ the coloring obtained by recoloring the ladder along $P$ starting either from $v$, if $v_1$ is frozen, or from $v_1$ otherwise. As before, at that point we are done except if both $v$ and $v_1$ are frozen in $\eta$. Note that, for $i \ge 3$, $\eta(v_i) = (i-1) \bmod 3$, because of the color shift of the ladder.

Let us consider the vertex $v_5$. It cannot have degree 2, because it is frozen in $\sigma$, and no degree-2 vertex can be frozen in a $\Delta+1$-coloring, with $\Delta \ge 3$. Hence, we can assume that $v_5$ has a neighbor $z$ outside $P$. And because $P$ is a shortest path, $z$ is at distance at least 4 from $v$. Also note that, since we assume that $r \ge 7$, $d(v, z) \le d(v, v_5) + 1 \le r - 1$. Therefore, by Lemma 4.2, $z$ is frozen in $\sigma$. We will use the following claim:

**Claim 4.5.** If $z$ is non-frozen in $\eta$, then a nice recoloring exists.

*Proof.* Indeed, from $\eta$, we can recolor along a ladder from $z$ to $v$. After this operation, no other vertex of the boundary is recolored, $v$ is non-frozen, and each vertex has been recolored at most twice. Hence, this defines a nice recoloring sequence. $\square$

We make a case analysis depending on the number of neighbors of $z$ in $P$.

**Case 1:** $z$ has a single neighbor in $P$. Since $z$ is frozen in $\sigma$, $v_5$ is its only neighbor colored with $\sigma(v_5)$. In $\eta$, $v_5$ is recolored with a different color, which implies that $z$ is no longer frozen in $\eta$. By Claim 4.5, the conclusion follows.

**Case 2:** $z$ has exactly two neighbors in $P$. Let $c_1$ and $c_2$ be the colors of these two neighbors in $\sigma$. Since $z$ is frozen in $\sigma$, it does not have two neighbors colored with the same color. Moreover, in $\eta$, the two neighbors of $z$ in $P$ have color $c'_1 = c_1 - 1 \bmod 3$ and $c'_2 = c_2 - 1 \bmod 3$ by Lemma 4.3 (since $z$ is incident to $v_5$, the other neighbor is at least $v_3$). Then we have $\{c_1, c_2\} \ne \{c'_1, c'_2\}$. It follows that $z$ is non-frozen in $\eta$, and the result follows from Claim 4.5.

**Case 3:** $z$ has at least three neighbors in $P$. Since $P$ is a shortest path, $z$ has exactly three neighbors in $P$, and these neighbors are consecutive in $P$. Let $3 \le i \le 5$ such that $v_i, v_{i+1}, v_{i+2}$ are the neighbors of $z$ in $P$. Since $z$ is adjacent to $v_{i+1}$, we have $\sigma(z) \ne \sigma(v_{i+1}) = (i+1) \bmod 3$. Let $P'$ be the path obtained from $P$ by replacing $v_{i+1}$ by $z$. (Note that $z$ is not in the boundary of $B$, and then $z \ne w$.) Then $P'$ is a shortest path from $v$ to $w$, and since $\sigma(z) \ne (i+1) \bmod 3$, we can apply Lemma 4.3 on $P'$ to conclude. More precisely, if $i=3$, then $(i+1)+3$ is at distance at most $r$ because $r \ge 7$, and if $i=4$ or $5$, then $(i+1)-3 \ge 2$, thus in both cases the lemma applies.

This concludes the proof, and proves Theorem 3.3.

## 4.2 Consequences of Theorem 3.3

The next lemma ensures that, in the centralized setting, we can obtain a 28-locally non-frozen coloring.

**Proposition 3.1.** Let $G$ be a connected graph of maximum degree $\Delta \ge 3$, and let $I$ be a maximal independent set at distance $d \ge 15$ in $G$. Let $\sigma$ be a coloring of $G$ that is
non-frozen. Then it is possible to transform $\sigma$ into a coloring $\mu$ where $I$ is non-frozen, with $O(n)$ single vertex recolorings.

**Proof.** We start by unfreezing a vertex of $I$. Consider a pair of vertices $u, v$ such that $u$ is non-frozen and $v$ is in $I$, that minimize the distance $d(u, v)$. Note that if $u = v$, we are done. Otherwise, we take a shortest path from $u$ to $v$ and build a ladder along this path to unfreeze $v$.

We construct an auxiliary graph $H$, where $V(H) = I$, and we put an edge $(i, i')$ in $H$ if there exists a path of length at most $2d$ from a vertex of $B(i, 7)$ to a vertex of $B(i', 7)$ in $G$ which does not contain any vertex in $B(i'', 7)$ for any $i'' \neq i, i'$. Note that for any pair $a, b \in I$, $B(a, 7)$ and $B(b, 7)$ are disjoint, since $d \geq 15$.

**Claim 4.6.** *The graph $H$ is connected.*

*Proof.* Suppose the claim does not hold. Let $A$ be a connected component of $H$. Let $i \in A$ and $j \in I \setminus A$, such that $d_G(i, j)$ is minimum among the such pairs. If $d(i, j) \geq 2d + 1$, then the vertex in the middle of a shortest path between $i$ and $j$ is at distance at least $d+1$ from any vertex in $I$ which contradicts the maximality of $I$. So there exists $i \in A$ and $j \in I \setminus A$ such that $d(j, i) \leq 2d$. Now let $x$ be the last vertex in $B(i, 7)$ and $y$ the last vertex in $B(j, 7)$. We have $d(x, y) \leq 2d$ which gives a contradiction. $\square$

Now, let us denote by $T$ a spanning tree of $H$ rooted in $v$. Let $\tau$ be a BFS ordering of $T$. The index of a vertex of $H$ is its position of appearance in the BFS. Let $i$ be the first vertex of $\tau$ that is frozen. Note that if all the vertices of $I$ are non-frozen, we are done. Also note that $i$ cannot be the root of the tree since $v$ is non-frozen.

**Claim 4.7.** *By recoloring a constant number of vertices, we can unfreeze $i$, and this operation leaves the vertices of index $j$ smaller than $i$ in $\tau$ non-frozen.*

*Proof.* Let $i'$ be the parent of $i$ in $T$, and let $P$ be the path from $i$ to $i'$ in $G$ corresponding to the edge $(i, i')$ in $H$. By definition, $P$ has length at most $2d$ and does not intersect $B(i'', 7)$ for any $i'' \neq i, i'$. Also, we can assume that $P$ is an induced path, since otherwise we can take a path on a subset of vertices of $P$, satisfying the same properties. If there is a vertex $y$ in $P \setminus B(i, 7)$ that is unfrozen, we simply recolor a ladder from $y$ to $i'$, to unfreeze $i'$. Otherwise, let $x$ be the last vertex of $P$ in $B(i, 7)$. By Theorem 3.3, by recoloring at most 14 vertices, we can recolor $x$, leave $i$ unfrozen and while recoloring only vertices in $B(i, 6)$ (and $x$). We can recolor a ladder from $x$ to $i'$ to get the conclusion. In both cases, the recoloring sequence has length at most $2d + 14$, and the non-frozen vertices of $I$ are kept unfrozen. $\square$

We iterate this construction to get all of $I$ non-frozen. This requires at most $(2d+14)|I| \leq (2d+14)n$ recoloring steps, therefore we get the result. Note that since every vertex contains at most $\Delta^{2d}$ other vertices of $I$ at distance at most $2d$, every vertex is recolored at most $O(\Delta^{2d})$ times during the whole process. $\square$

We now prove the following proposition, which is the local analogue of the previous proposition. Intuitively, it says that if we have a well-spread set of non-frozen vertices, we move it to another well-spread set locally.
**Proposition 3.2.** Let $G$ be a connected graph of maximum degree $\Delta \ge 3$, and let $I$ be a maximal independent set at distance $d \ge 15$ in $G$. Let $\sigma$ be a $r$-locally non-frozen coloring. Then it is possible to transform $\sigma$ into a coloring $\mu$ where $I$ is non-frozen, in $O(d\Delta^{4d+10} + d\log^*n+r)$ rounds, and with a schedule of length $O((r+d)d\Delta^{6d+10})$ in the LOCAL model.

Note that $r$ could be large and depend on $n$, in which case Proposition 3.2 not only
moves the set of well-spread non-frozen vertices around, but also makes it more dense.

*Proof.* Let $N$ be the set of non-frozen vertices at the beginning of the algorithm. We proceed in two steps: first, we show that we can somehow move the set of non-frozen vertices to a subset of $I$, and then we show how to unfreeze all the vertices of $I$.

For both steps, we will use an auxiliary coloring of the vertices of $I$. Note that this auxiliary coloring is just a tool and is independent of the coloring we are modifying. Let $p$ be an integer. Consider a graph $H$, whose vertex set is $I$ and whose edges are the pairs $(a, b) \in I$, such that $d_G(a, b) \le p$. The graph $H$ has maximum degree $\Delta_H = O(\Delta^p)$, thus we can compute a $(\Delta_H + 1)$-coloring of $H$ in $O(\Delta_H + \log^*(|H|))$ rounds in $H$ [1]. Therefore, we can compute such an auxiliary coloring of $I$ in $G$ in $O(p\Delta^p + p\log^*n)$ rounds (in $G$).

**Claim 4.8.** We can reach a coloring such that in the final coloring any vertex of $I$ is at distance at most $r+d$ from a non-frozen vertex of $I$, with a schedule of length $O(d\Delta^{2d+4})$ computed in $O(d\Delta^{2d+2} + d\log^*n)$ rounds.

*Proof.* Consider an auxiliary coloring as described above, with $p = 2d + 2$. Let $M_i$ be the set of vertices that are in $I$ and have received color $i$ in $H$. We will go through the sets $M_i$ one after another. At step $i$, for every $u \in M_i$ that is frozen, if $B(u, d)$ contains a vertex $v$ of $N$ that is still non-frozen, we recolor a ladder from $v$ to $u$ (where we take $v$ to be the closest non-frozen vertex). Since, $p = 2d + 2$, the balls $B(u, d+1)$ with $u \in M_i$ are all disjoint by construction of the $M_i$. Therefore, we can perform this step in parallel without coordination. Now, we want the additional property that a vertex $u$ of $I$ that has been unfrozen cannot be refrozen. This could happen if there is a non-frozen vertex in the neighborhood of $u$ that is the start of a ladder (thus at distance exactly $d$ from another vertex of $I$). We add a twist to the algorithm: if this situation occurs, we do not build the ladder.

To prove that the claim holds at the end of this process, consider a vertex $w$ of $I$. By assumption, at the beginning $w$ was at distance at most $r$ from a non-frozen vertex $x$ of $N$. Consider a vertex $u$ of $I$ in $B(x, d)$ (such a vertex exists by maximality). If this vertex $u$ is non-frozen, then the claim holds for $w$. If this vertex is frozen, the only possibility is that we did not build a ladder from $x$ to $u$ because of the twist in the algorithm. But in this case there exists a vertex $u' \in I$ in the neighborhood of $x$ which is necessarily non-frozen (since there is no obstruction to building a ladder from $x$ to $u'$).

The round complexity is dominated by the computation of the auxiliary coloring, and the schedule length can be bounded by the maximum size of a ladder inside a ball, $O(d)$ times the number of color classes $O(\Delta^{2d+4})$. $\square$

**Claim 4.9.** Consider a coloring and the distance from any vertex of $I$ to the closest non-frozen vertex of $I$ in this coloring. If this distance is positive, we can reach a new
coloring, where this distance in strictly smaller, with a schedule of length $O(\Delta^{6d+14})$ in $O(d\Delta^{4d+10} + d \log^* n)$ rounds.

*Proof.* Again, consider an auxiliary coloring as described at the beginning of the proof, but with parameter $p = 4d+10$. We will consider the color classes $M_i$, one after another. For every $u \in M_i$, let $X_u$ be the ball $B(u, 2d+4)$ plus the vertices of $I$ at distance exactly $2d+5$ from $u$ in $G$. Note that no vertex of $I$ in $V\setminus X_u$ is adjacent to $X_u$. If $u$ is non-frozen, then we can unfreeze all the vertices of $I \cap X_u$: since $d \ge 15$, we can proceed exactly like in the proof of Proposition 3.1. Note that, similarly to the previous proof, because of our definition of the sets $(X_u)_u$, these recolorings can be performed in parallel, and no vertex of $I$ that was non-frozen can be refrozen.

We claim that, at the end of this recoloring, the minimum distance from any vertex $u$ of $I$ to the closest non-frozen vertex of $I$ has decreased. Indeed, let $v$ be the closest non-frozen vertex of $I$ from $u$ at the beginning. If $d(u, v) \le 2d+4$, $u$ is non-frozen at the end of the algorithm by construction. Otherwise, let $x$ be the $(d+1)$-th vertex of a shortest path from $v$ to $u$. Note that $x$ must be at distance at most $d$ from a vertex $v'$ of $I$. Thus $v'$ is in $B(v, 2d+1)$. So $v'$ is unfrozen at the end of the algorithm. And since the distance from $u$ to $v'$ is strictly smaller than the one from $u$ to $v$, we get the condition of the claim. The computation of the schedule length and number of rounds are similar to the ones of the previous claim, except the unfreezing of each $X_u$ uses $O(\Delta^{2d+4})$ recoloring steps. $\square$

By using the algorithm of Claim 4.8, and then iterating the algorithm of Claim 4.9, we can unfreeze all of $I$.

The number of iteration of Claim 4.9 is at most $r+d$ by Claim 4.8, thus the total schedule length is in $O((r+d)d\Delta^{6d+10})$. The total number of rounds is $O(d\Delta^{4d+10} + d \log^* n + r)$ since we can reuse the same auxiliary coloring for all the iterations. $\square$

# 5 Recoloring locally non-frozen colorings

The goal of this section is to prove Proposition 3.4. To do so we will first prove a few lemmas.

## 5.1 Degeneracy ordering lemma

A graph $G$ is *d-degenerate* if any subgraph of $G$ admits a vertex of degree at most $d$. In other words, there exists an ordering $v_1, \dots, v_n$ of the vertices such that for every $i \le n$, the vertex $v_i$ has at most $d$ neighbors in $v_{i+1}, \dots, v_n$.

**Lemma 5.1.** Let $G$ be a connected $r$-locally non-frozen graph which is $k$-colorable, and let $S$ be a maximal independent set at distance at least $2r+2$. Let $B_S$ be the set of vertices at distance at most $r$ from $S$, and $G' = G \setminus B_S$.

Then there exists a $(\Delta-1)$-degeneracy ordering of $G'$ consisting of $O(r \cdot k)$ consecutive independent sets. Moreover, if we are given a $k$-coloring $c$ of $G'$, such an ordering can be found in $O(r)$ rounds in the LOCAL model.
*Proof.* The graph $G'$ is $(\Delta - 1)$-degenerate because we have removed at least one vertex from a connected graph of maximum degree $\Delta$. The degeneracy ordering of $G'$ will be built by first splitting $G'$ into layers such that each vertex $v$ in layer $i$ has at most $\Delta - 1$ neighbors in layers $j \ge i$. Then we will split each layer into independent sets using the coloring $c$.

We define the $i$-th layer $L_i$ of $G'$ as the set of vertices at distance exactly $i$ from $B_S$. Since $S$ is a maximal independent set at distance $2r+2$, all the vertices of $G'$ belong to a layer $i$ with $i \le r+2$. All the vertices in the first layer have a neighbor in $B_S$ and, for every $i \ge 2$, all the vertices in layer $i$ have at least one neighbor in layer $(i-1)$. So the graph induced by the layers $\cup_{j \ge i} L_j$ is $(\Delta - 1)$-degenerate (and all the vertices of $L_i$ have degree $\Delta - 1$ in $\cup_{j \ge i} L_j$). We now split each layer into $k$ independent sets using the color classes of a $k$-coloring $c$. We can order the vertices in the layers by color, and get a $(\Delta - 1)$-degeneracy ordering of $G'$ composed of $O(r \cdot k)$ consecutive independent sets.

Note that in the LOCAL model, if $S$ is given, computing this partition can be done in $O(r)$ rounds. Indeed, after computing its distance to $S$, each vertex knows if it is in $B_S$ or in which layer it is. As their color in $c$ is given as input, they do not need more information. $\square$

## 5.2 List-coloring lemma

The following lemma is a list-coloring adaptation of a proof of Dyer et al. [19] that ensures that one can transform any $(d+2)$-coloring of a $d$-degenerate graph into any other. Let $G$ be a graph in which, for every vertex $u$, we are given a list $L_u$ of colors. A coloring $c$ of $G$ is *compatible* with the lists $L_u$, if the coloring is proper and for every vertex $u$, $c(u) \in L_u$. Let $\tau$ be an ordering of $V(G)$. We denote by $d_{\tau}^{+}(u)$ (or $d^{+}(u)$), when $\tau$ is clear from context) the number of neighbors of $u$ that appear after $u$ in $\tau$. We say that a set of lists is *safe for $\tau$* if, for every vertex $u$, $|L_u| \ge d_{\tau}^{+} + 2$.

We will consider particular schedules in the LOCAL model such that, at each step, all the recolored vertices are recolored from a color $a$ to a color $b$ (in particular, the recolored vertices form an independent set). We call such a reconfiguration step an $a \to b$ step. A recoloring schedule where all the steps are $a \to b$ steps is called a *restricted schedule*. Note that any schedule can be transformed into a restricted schedule by multiplying the length of the schedule by $O(k^2)$ (where $k$ is the total number of colors). Indeed, we simply have to split each step $s$ of the initial schedule into $k(k-1)/2$ different $a \to b$ steps $s_{a,b}$ for every pair of colors $a, b$. At step $s_{a,b}$, we recolor from $a$ to $b$ all the vertices recolored from $a$ to $b$ at step $s$. Note that since at step $s$, the set of recolored vertices is an independent set, all the intermediate colorings obtained after $s_{a,b}$ are proper.

**Lemma 5.2.** Let $G$ be a graph, $\tau$ be an ordering of $G$ composed of $t$ consecutive independent sets and, $d = \max_{v \in V} d_{\tau}^{+}(u)$. Consider a set of lists $(L_v)_{v \in V}$ safe for $\tau$. Let $\sigma, \eta$ be two $k$-colorings of $G$ compatible with $(L_v)_{v \in V}$.

There exists a recoloring sequence from $\sigma$ to $\eta$ with a restricted schedule of length at most $k^{t+1}$ where $k = |\cup_{v \in V} L_v|$. Moreover, this schedule can be found in $O(r)$ rounds if the independent sets of $\tau$ are given.

*Proof.* Let $I_t, \dots, I_1$ be the independent sets of the ordering $\tau$. For every $i \le t$, we denote by $G_i$ the graph $G[\cup_{j \le i} I_j]$.
Let us prove by induction on $i$ that we can recolor $G_i$ from $\sigma_{G_i}$ to $\eta_{G_i}$ with a restricted schedule of length at most $k^{i+1}$. Since $G_1$ induces an independent set, a restricted schedule of length $k \cdot (k-1) \le k^2$ exists. Indeed, for every pair $a \ne b$, we create an $a \to b$ step where we recolor the vertices of $I_1$ colored $a$ in $\sigma$ and $b$ in $\eta$ from color $a$ to color $b$. After all these steps, the coloring is $\eta_{G_1}$. Since $I_1$ is an independent set, we indeed recolor an independent set at any step.

In order to extend the transformation of $G_{i-1}$ into a transformation of $G_i$ (with $i \ge 2$) we perform as follows. For each step $s$ of the transformation of $G_{i-1}$, we will add $(k-2)$ new steps before $s$. Since the transformation is a restricted schedule, there exists $a, b$ such that $s$ is an $a \to b$ step. For every $c \ne a, b$, we add a $b \to c$ step, denoted $s_{b,c}$, between $s$ and the step before in the transformation of $G_{i-1}$. Let $I$ be the set of vertices recolored at step $s$, and $N_I$ be the set of vertices at distance exactly 1 from a vertex of $I$. In $s_{b,c}$, we recolor all the vertices of $G_i \cap N_I$ colored $b$ with the color $c$, if it is possible (i.e. if $c$ is in their lists, and they do not have any neighbor already colored $c$). Note that every vertex $v$ of $I$ colored $b$ can indeed be recolored with some color $c$, distinct from $a$, since the size of the list of $v$ is at least the degree of $v$ plus two in $G_i$. So after these new steps, we can safely apply the $a \to b$ step without creating monochromatic edges in $G_i$.

Finally, at the end of the reconfiguration sequence of $G_{i-1}$, we add $k \cdot (k-1)$ steps in order to recolor the vertices of $I_i$ with their target colors (after $G_{i-1}$ has reached its target coloring) as we did for $I_1$. This provides a restricted schedule of length $(k-2) \cdot k^i + k \cdot (k-1) \le k^{i+1}$ from $\sigma$ to $\eta$ which completes the proof.

In the LOCAL model, to compute their own layers, the vertices need $O(r)$ rounds. In order to compute its own schedule, a vertex simulates the induction, above, which can be done with a view of $O(r)$ rounds. $\square$

As an immediate corollary, we obtain the following, where the lists are just the same $k$ colors for every vertex:

**Lemma 5.3.** Let $G$ be a $d$-degenerate graph and $\sigma, \eta$ be two $k$-colorings of $G$ with $k \ge d+2$. Assume that $G$ has a degeneracy ordering composed of $t$ consecutive independent sets. Then there exists a recoloring sequence from $\sigma$ to $\eta$ with a restricted schedule of size at most $k^{t+1}$ in the LOCAL model.

## 5.3 Recoloring outside the balls

Let us now prove that we can obtain a coloring where the vertices agree on $V \setminus B_S$. Then we will explain how we can transform such a coloring into the target coloring by recoloring (almost) only vertices of $B_S$.

**Lemma 5.4.** Let $k \ge \Delta + 1$ and $r \ge 10$. Let $G$ be a graph of maximum degree $\Delta \ge 3$, and let $\sigma, \eta$ be two $r$-locally non-frozen $k$-colorings of $G$. Let $S$ be a maximal independent set at distance $r' \ge 2r + 2$. Let $G' = G[V \setminus B_S]$ where $B_S = \cup_{x \in S} B(x, r)$.

Then there is a recoloring schedule of length $k^{O(r'k)}$ from $\sigma$ to $\eta'$ such that $\eta'_{G'} = \eta_{G'}$.

*Proof.* The first part of the recoloring sequence is a pre-processing step to ensure that every vertex $v \in S$ is non-frozen. Since $\sigma$ is $r$-locally non-frozen, for every $v$ in $S$, there is a vertex $u$ in $B(v, r)$ such that $u$ is non-frozen. By recoloring a ladder along a shortest path from $u$ to $v$, $v$ is non-frozen. Since $B(v, r)$ does not share an edge with $B(v', r)$
for any $v, v' \in S$, we can repeat this argument for every $v \in S$ and then assume that $S$ is unfrozen. In the LOCAL model, all these recolorings pre-processing steps can be performed in parallel. So, from now on, we can assume that, in $\sigma$, every vertex of $S$ is non-frozen (and we will keep this property all along the schedule).

By Lemma 5.1 and Lemma 5.3, there exists a restricted recoloring schedule $\mathcal{R}$ in $G'$ from $\sigma_{G'}$ to $\eta_{G'}$ in at most $(\Delta + 2)^{O(r\Delta)}$ steps.

Let us now explain how we can extend the restricted schedule $\mathcal{R}$ of $G'$ to $G$, that is, avoid the conflicts between vertices in $G'$ and their neighbors in $G$ that are in $B_S$. Let $X$ be the set of vertices which are recolored during an $a \to b$ step of $\mathcal{R}$. Denote by $Y$ the set of vertices of $B_S$ such that $Y$ is adjacent to a vertex of $X$. We will recolor these vertices, before they create any conflict.

For each ball of radius $r$ centered in $u \in S$, we first identify the vertices of $Y_u = Y \cap B(u, r)$ that are colored $b$. Note that $Y_u$ is an independent set. By Theorem 3.3, we can recolor each vertex of $Y_u$ in at most $2r$ steps with a different color, leaving $u$ unfrozen, and without modifying the color of any other vertex in $Y_u$. Since $Y_u$ contains at most $\Delta^r$ vertices, we can change the color of all the vertices of $Y_u$ with a schedule of length at most $2r \cdot \Delta^r$. Since all the balls of radius $r$ centered in $S$ are disjoint and do not share an edge, we can perform these schedules in parallel for each ball of radius centered in $S$.

Since the restricted schedule $\mathcal{R}$ has length at most $k^{O(r'k)}$, the new schedule have length at most $k^{O(r'k)} \cdot 2r'k^{k+2} = k^{O(r'k)}$, which completes the proof. $\square$

The previous lemma ensures that, from any locally non-frozen coloring, we can obtain a locally non-frozen coloring where all the vertices but the vertices of $B_S$ are colored with the target coloring. Before completing the proof of Proposition 3.4, we need one more lemma.

## 5.4 Recoloring inside the balls (easy case)

**Lemma 5.5.** Let $k \ge \Delta + 1$. Let $\sigma$ and $\eta$ be two $k$-colorings of a graph $G$ which only differ on $X \subseteq V$. Assume that, in each connected component $C$ of $G[X]$, there exists a vertex that has degree at most $k-2$ or has two neighbors in $V \setminus X$ colored the same. Then there is a recoloring schedule from $\sigma$ to $\eta$ of length at most $k^{O(\mathrm{diam}(X)k)}$.

*Proof.* Let $C$ be a connected component of $X$. For every vertex $v$ of $G[C]$, let $Z_v$ be the set of colors $\sigma$ that appear on neighbors outside $X$, that is on $N(v) \cap (V \setminus X)$. We assign to every vertex $v$ of $G[C]$ the list of colors $[k] \setminus Z_v$. Note that since the total number of colors is $k \ge \Delta + 1$, every vertex $x \in C$ has a list of size at least $d_{G[X]}(x) + 1$. Moreover, if a vertex $x$ has degree at most $k-2$ in $G$, or two neighbors of $x$ are colored the same in $V \setminus X$, its list has size $d_{G[X]}(x) + 2$. We claim that we can build a degeneracy ordering of $C$ for which the lists of $C$ are safe, and that consists of $\mathrm{diam}(C)k$ consecutive independent sets. Indeed, similarly to earlier in the paper, we can take the vertices of $C$ by layers, corresponding to the distance from $x$, and then split these layers into independent sets using the colors of $\sigma$.

Finally, by Lemma 5.3, there exists a recoloring sequence of $G[C]$ from $\sigma$ to $\eta$ which recolors each vertex at most $k^{O(\mathrm{diam}(C)k)}$ times. Since we can treat each connected component of $X$ simultaneously (there is no edge between them), the conclusion follows. $\square$
## 5.5 Finishing the proof of Proposition 3.4

All the previous lemmas can be combined in order to prove Proposition 3.4, that we restate here.

**Proposition 3.4.** Let $G$ be a graph with $\Delta \ge 3$ and $I$ be an independent set at distance 28. Let $r, k, k' \in \mathbb{N}$ such that $k' < k, k \ge \Delta+1$. Let $\mu, \gamma$ be two colorings, using respectively at most $k$ and $k'$ colors, that are both non-frozen on $I$. There is a recoloring schedule from $\mu$ to $\gamma$ of length at most $(k')^{O(\Delta)}$. Moreover, such a recoloring schedule can be computed in $O(\Delta)$ rounds in the LOCAL model.

*Proof of Proposition 3.4.* Let us fix $r=7$. Let $I$ be a maximal independent set at distance $r'=2r+14$. Let $G'=G\setminus B_I$ where $B_I = \cup_{x \in I} B(x, r)$. By Lemma 5.4, there is a coloring $\eta'$ which agrees with $\eta$ on $G\setminus B_I$ and a recoloring schedule from $\sigma$ to $\eta'$ of length at most $k^{O(kr)}$. To conclude, we only need to find a recoloring sequence from $\eta'$ to $\eta$, that is to prove that we can recolor all the balls of $B_I$ with their target coloring $\eta$.

For every ball $B_v$ of radius $r$ centered in $v \in I$, we will define a set $B_v'$ which contains $B_v$, is included in $B(v, r+5)$, and that satisfies the conditions of Lemma 5.5. Since $I$ is an independent set at distance $2r+14$, for every $v, w \in I$, the sets $B_v'$ and $B_w'$ will be at distance at least 4. Let $B_I' = \cup_{v \in I} B_v'$. Since the diameter of each ball $B_v'$ for $v \in S$ is $O(r)$ and all the balls of $B_S'$ are disjoint, we will conclude using Lemma 5.5. In the rest of the proof, we restrict to a single ball $B_v$ for $v \in I$ denoted by $B$ for simplicity.

If a vertex of $B$ has two neighbors in $V \setminus B$ colored the same or has degree less than $k-2$, we set $B' = B$. Otherwise, let us prove that by adding a few vertices to $B$ and doing a few recoloring steps, we can apply the Lemma 5.5. Note that no vertex of $V \setminus B$ is colored with $k$ in $\eta'$, since it agrees with $\eta$, which is a $k'$-coloring with $k' < k$ by assumption.

Let us consider a path $v_1, v_2, \dots, v_6$ of vertices such that $v_i$ is at distance $i$ from $B$. For every $i \in \{3, 4, 5\}$, we can remark we can obtain a desired set $B'$ if one of the following holds:

* If $\deg(v_i) < \Delta$, then we simply take $B' = B \cup_{j \le i} v_i$ which contains a vertex of degree less than $\Delta$.

* If $N(v_i) \setminus v_{i-1}$ is not a clique then let $a, b$ be two neighbors of $v_i$ that are non-adjacent. Then, since $d(a, B)$ and $d(b, B)$ are at least two, we can recolor $a$ and $b$ with $k$ in $\eta'$ (the coloring is proper since color $k$ was not used in $\eta$ by assumption). Now, in this new coloring, $B' = B \cup_{j \le i} v_i$ satisfies the condition. (We will recolor $a$ and $b$ to the right color at the very end of the algorithm.)

Let us now prove that one of the conditions above must hold. Assume, for the sake of contradiction, that for every $3 \le i \le 5$, $N(v_i) \setminus v_{i-1}$ is a clique and that all the $v_i$'s have degree at least $\Delta$.

Let $z$ be a vertex of $N(v_3)$ distinct from $v_2$ and $v_4$ (which exists since $\Delta \ge 3$). The vertex $z$ is at distance at most 4 from $B$. Moreover, $v_4z$ is an edge (otherwise $N(v_3) \setminus v_2$ is not a clique). Since $N(v_4) \setminus v_3$ is a clique, $zv_5$ must also be an edge. But then $N(v_5) \setminus v_4$ cannot be a clique: that would mean that $z$ and $v_6$ are adjacent, and then $v_6$ would be at distance 5 from $B$, which is a contradiction.
Now, by Lemma 5.5, we can recolor all the vertices of $B'$ with the target coloring $\eta$ in such a way that every vertex of $B'$ is recolored at most $\Delta^{O(\Delta^r)}$ times (since the diameter of $B'$ is at most the diameter of $B$ plus 5). We then finally recolor, if needed, the two vertices recolored $k$ in the second item of the construction of $B'$ with their real target color in $\eta$.

Since all the balls $B'$ are disjoint and do not share an edge, we can apply these steps in parallel. Moreover, since they are at distance at least 4, the fact that we recolor a vertex at distance 5 from $B$ can also be done in parallel. This completes the proof of Proposition 3.4. □

**Acknowledgments.** We would like to thank Valentin Gledel for fruitful discussions are the early stage of the project, as well as Quentin Ferro for his helpful study on the specific case of toroidal grids.

## References

[1] L. Barenboim, M. Elkin, and F. Kuhn. Distributed (Δ + 1)-coloring in linear (in Δ) time. *SIAM J. Comput.*, 43(1):72–95, 2014.

[2] V. Bartier, N. Bousquet, C. Feghali, M. Heinrich, B. Moore, and T. Pierron. Recolouring planar graphs of girth at least five. *arXiv preprint arXiv:2112.00631*, 2021.

[3] V. Bartier, N. Bousquet, and M. Heinrich. Recoloring graphs of treewidth 2. *Discret. Math.*, 344(12):112553, 2021.

[4] M. Bonamy and N. Bousquet. Recoloring graphs via tree decompositions. *Eur. J. Comb.*, 69:200–213, 2018.

[5] M. Bonamy, N. Bousquet, and G. Perarnau. Frozen (Δ + 1)-colourings of bounded degree graphs. *Combinatorics, Probability and Computing*, 30(3):330–343, 2021.

[6] M. Bonamy, M. Johnson, I. Lignos, V. Patel, and D. Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. *Journal of Combinatorial Optimization*, pages 1–12, 2012.

[7] M. Bonamy, P. Ouvrard, M. Rabie, J. Suomela, and J. Uitto. Distributed recoloring. In *32nd International Symposium on Distributed Computing, DISC 2018*, volume 121 of *LIPIcs*, pages 12:1–12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.

[8] P. S. Bonsma and L. Cereceda. Finding paths between graph colourings: Pspace-completeness and superpolynomial distances. *Theor. Comput. Sci.*, 410(50):5215–5226, 2009.

[9] N. Bousquet, L. Feuilloley, M. Heinrich, and M. Rabie. Distributed recoloring of interval and chordal graphs. In Q. Bramas, V. Gramoli, and A. Milani, editors, *25th International Conference on Principles of Distributed Systems, OPODIS 2021*, volume 217 of *LIPIcs*, pages 19:1–19:17, 2021.
[10] N. Bousquet and M. Heinrich. A polynomial version of cereceda's conjecture. *Journal of Combinatorial Theory, Series B*, 155:1–16, 2022.

[11] N. Bousquet and G. Perarnau. Fast recoloring of sparse graphs. *Eur. J. Comb.*, 52:1–11, 2016.

[12] K. Censor-Hillel, Y. Maus, S. R. Peled, and T. Tonoyan. Distributed vertex cover reconfiguration. In *13th Innovations in Theoretical Computer Science Conference, ITCS 2022*, volume 215 of *LIPIcs*, pages 36:1–36:23, 2022.

[13] K. Censor-Hillel and M. Rabie. Distributed reconfiguration of maximal independent sets. *J. Comput. Syst. Sci.*, 112:85–96, 2020.

[14] L. Cereceda. *Mixing Graph Colourings*. PhD thesis, London School of Economics and Political Science, 2007.

[15] L. Cereceda, J. van den Heuvel, and M. Johnson. Mixing 3-colourings in bipartite graphs. *Eur. J. Comb.*, 30(7):1593–1606, 2009.

[16] S. Chen, M. Delcourt, A. Moitra, G. Perarnau, and L. Postle. Improved bounds for randomly sampling colorings via linear programming. In *Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019*, pages 2216–2234, 2019.

[17] R. Diestel. *Graph Theory*, volume 173 of *Graduate Texts in Mathematics*. Springer-Verlag, Heidelberg, third edition, 2005.

[18] Z. Dvorák and C. Feghali. An update on reconfiguring $10$-colorings of planar graphs. *Electron. J. Comb.*, 27(4):P4.51, 2020.

[19] M. Dyer, A. D. Flaxman, A. M. Frieze, and E. Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. *Random Structures & Algorithms*, 29(4):450–465, 2006.

[20] C. Feghali. Paths between colourings of sparse graphs. *Eur. J. Comb.*, 75:169–171, 2019.

[21] C. Feghali, M. Johnson, and D. Paulusma. A reconfigurations analogue of brooks' theorem and its consequences. *Journal of Graph Theory*, 83(4):340–358, 2016.

[22] A. Frieze and E. Vigoda. A survey on the use of markov chains to randomly sample colourings. *Oxford Lecture Series in Mathematics and its Applications*, 34:53, 2007.

[23] M. Ghaffari and F. Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In *62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021*, page To appear. IEEE, 2022.

[24] N. Nishimura. Introduction to reconfiguration. *preprint*, 2017.

[25] A. Panconesi and A. Srinivasan. The local nature of Δ-coloring and its algorithmic applications. *Combinatorica*, 15(2):255–280, 1995.
[26] J. Suomela. Survey of local algorithms. *ACM Computing Surveys (CSUR)*, 45(2):1–40, 2013.

[27] J. van den Heuvel. *The Complexity of change*, page 409. Part of London Mathematical Society Lecture Note Series. Cambridge University Press, S. R. Blackburn, S. Gerke, and M. Wildon edition, 2013.

[28] E. Vigoda. Improved bounds for sampling colorings. In *40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA*, pages 51–59, 1999.