Nicolas Bousquet

Laurent Feuilloley

Mikaël Marc Heinrich

Mikaël Rabie

Rabie Short

Short and local transformations between (∆ + 1)-colorings *

à 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.

Introduction

Reconguration problems consist in nding 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 reconguration eld, the reader is referred to the two recent surveys on the topic [START_REF] Nishimura | Introduction to reconguration[END_REF][START_REF] Van Den | The Complexity of change[END_REF]. 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 denitions and notations on graphs, we refer the reader to [START_REF] Diestel | Graph Theory[END_REF]. A (proper) k-coloring of G is a function σ : V (G) → {1, . . . , k} such that, for every edge xy ∈ E, we have σ(x) = σ(y). Throughout the paper, we only consider proper colorings, and will then omit the word proper for brevity. The chromatic number χ(G) of a graph G is the smallest k such that G admits a k-coloring. Two k-colorings are adjacent if they dier on exactly one vertex. The k-reconguration graph of G, denoted by G(G, k), and dened for any k χ(G), is the graph whose vertices are k-colorings of G, with the adjacency relation dened above.

In this work, we will focus on the diameter of the reconguration graph. The krecoloring 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 reconguration 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 reconguration graph ensures the ergodicity of the Markov chain 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. [START_REF] Chen | Improved bounds for randomly sampling colorings via linear programming[END_REF][START_REF] Frieze | A survey on the use of markov chains to randomly sample colourings[END_REF]).

If we consider (∆ + 2)-colorings2 , 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 -)∆ [START_REF] Chen | Improved bounds for randomly sampling colorings via linear programming[END_REF], slightly improving a classical result of Vigoda [START_REF] Vigoda | Improved bounds for sampling colorings[END_REF]. 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 [START_REF] Feghali | A recongurations analogue of brooks' theorem and its consequences[END_REF] proved that the situation is not that bad for (∆ + 1)-colorings, since the reconguration 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 2 ). In other words, any non-frozen coloring can be transformed into any other with O(n 2 ) single vertex recolorings. In addition, Bonamy, Bousquet, and Perarnau [START_REF] Bonamy | Frozen (∆+ 1)-colourings of bounded degree graphs[END_REF] proved that, if G is connected, then the proportion of frozen (∆ + 1)-colorings of G is exponentially smaller than the total number of colorings.

Our results

Our main result consists in proving that we can bring the quadratic term in the result of Feghali, Johnson, and Paulusma [START_REF] Feghali | A recongurations analogue of brooks' theorem and its consequences[END_REF] down to a linear term (by paying an additional function of ∆).

Theorem 1.1. Let G be a connected graph with ∆ 3 and σ, η be two non-frozen kcolorings of G with k ∆ + 1. Then we can transform σ into η with a sequence of at most O(∆ c∆ 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 (∆)•n. The existence of linear transformations between colorings received considerable attention in recent years, see e.g. [START_REF] Bartier | Recoloring graphs of treewidth 2[END_REF][START_REF] Bartier | Recolouring planar graphs of girth at least ve[END_REF][START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF][START_REF] Dvorák | An update on reconguring $10$-colorings of planar graphs[END_REF]. 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 nal 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 ∆) 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 eciently in the LOCAL model of distributed computing

.

More formally, a recoloring (parallel) schedule of length r from α to β is a sequence of independent sets S 1 , . . . , 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 ∆ 3, k ∈ N with k ∆ + 1. Let σ, η be two k-colorings of G which are r-locally non-frozen. There exists three constants c, c , c such that we can transform σ into η with a parallel schedule of length at most

O(k c∆ + ∆ c r) in O(∆ c + log * n + k) rounds if k ∆ + 2. O(∆ c + log 2 n • log 2 ∆ + 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 3 See Section 1.2 for formal denitions on distributed algorithms. log 2 n) term in the number of rounds is there to compute a maximal independent set at distance Ω(1) (or a ∆ + 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 (∆ + 1)-coloring, if a vertex x is nonfrozen, 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 (∆ + 1)-colorings, we can locally duplicate 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 dierent from the one of Feghali et al. [START_REF] Feghali | A recongurations analogue of brooks' theorem and its consequences[END_REF], whose proof is based on an iterative identication 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 ∆ by a polynomial function of ∆. We actually have no lower bound that ensures that a dependency in ∆ is necessary. In other words: Question 1.3. Given α, β two non-frozen (∆ + 1)-colorings, is it possible to transform α into β in O(n) steps independent of ∆?

A rst step towards this question would consist in proving that if the number of colors is large enough (compared to ∆), then we can remove or reduce the dependency on ∆. When k = ∆ + 2, a result of Bonamy and Bousquet [START_REF] Bonamy | Recoloring graphs via tree decompositions[END_REF] (on recolorings with the grundy coloring number) ensures that the diameter is at most O(∆n). One can wonder if this dependency in ∆ can be avoided.

Finally note that, at some steps of the proof, we can reduce the exponential dependency on ∆ into a polynomial one by adapting a result of Bousquet and Heinrich [START_REF] Bousquet | A polynomial version of cereceda's conjecture[END_REF] but we did not succeed to do it at every step. We thus decided to keep the proof as simple as possible.

LOCAL model and distributed recoloring

The LOCAL model is a classic model of distributed computing (see [START_REF] Suomela | Survey of local algorithms[END_REF] for a survey). The model consists of a graph G = (V, E) where each vertex v ∈ V has a unique identier.

Each edge corresponds to a communication link between two vertices. Initially, each vertex only has access to its identier and its list of neighbors. Each vertex communicates synchronously with its neighbors at each round. We say that an algorithm runs in rounds, if every vertex can run this algorithm for 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 , 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 diers 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 [START_REF] Bonamy | Distributed recoloring[END_REF], and implicitly studied before in [START_REF] Panconesi | The local nature of ∆-coloring and its algorithmic applications[END_REF]. In [START_REF] Bonamy | Distributed recoloring[END_REF], the authors focus on recolorings 3-colored trees, subcubic graphs and toroidal grids, and in [START_REF] Panconesi | The local nature of ∆-coloring and its algorithmic applications[END_REF], the focus is on transforming a (∆ + 1)-coloring into a ∆-coloring. More recently, [START_REF] Bousquet | Distributed recoloring of interval and chordal graphs[END_REF] designed ecient distributed recoloring for chordal and interval graphs. A few reconguration problems dierent from coloring have been studied in the distributed setting, including vertex cover [START_REF] Censor-Hillel | Distributed vertex cover reconguration[END_REF] and maximal independent sets [START_REF] Censor-Hillel | Distributed reconguration of maximal independent sets[END_REF].

Distributed recoloring in the LOCAL model is dened 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 , . . . , c = c end of length , 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 diers from its neighbors', and (ii) if its color changes at some step i > 0 (i.e. c i-1 = c i ), then the color of none of its neighbors is modied 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 [START_REF] Bonamy | Distributed recoloring[END_REF] on distributed recoloring. One problem studied in [START_REF] Bonamy | Distributed recoloring[END_REF] consists in recoloring 3-colored graphs of maximum degree 3 with the help of an extra color. They provide an algorithm that nds 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 [START_REF] Bonamy | Distributed recoloring[END_REF]:

The rst question is about the complexity of nding a schedule to recolor a ∆coloring with an extra color. Theorem 1.2 gives an algorithm that nds a parallel schedule of length f (∆) in O(F (∆) log * n) communication rounds (since these ∆colorings can be seen as non-frozen (∆ + 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 avor can be found in [START_REF] Censor-Hillel | Distributed reconguration of maximal independent sets[END_REF] for the problem of maximal independent set reconguration but we did not manage to adapt it in our setting.

Related work in graph recoloring

Bonsma and Cereceda [START_REF] Bonsma | Finding paths between graph colourings: Pspacecompleteness and superpolynomial distances[END_REF] proved that there exists a family G of graphs and an integer k such that, for every graph G ∈ G, there exist two k-colorings whose distance in the kreconguration graph is nite and super-polynomial in n. Cereceda conjectured that the situation is dierent 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 , . . . , v n of the vertices such that for every i n, the vertex v i has at most d neighbors in v i+1 , . . . , v n . It was shown independently in [START_REF] Dyer | Randomly coloring sparse random graphs with fewer colors than the maximum degree[END_REF] and [START_REF] Cereceda | Mixing 3-colourings in bipartite graphs[END_REF] that for any d-degenerate graph G and every k d + 2, 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 [START_REF] Cereceda | Mixing Graph Colourings[END_REF] conjectured that the diameter of G(G, k) is of order O(n 2 ), as long as k d + 2. If correct, the quadratic function is sharp, even for paths or chordal graphs as proved in [START_REF] Bonamy | Reconguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF]. The best known bound on this conjecture is due to Bousquet and Heinrich [START_REF] Bousquet | A polynomial version of cereceda's conjecture[END_REF], who proved that the diameter of G(G, k) is n d+1 . The conjecture is known to be true for a few graph classes, such as chordal graphs [START_REF] Bonamy | Reconguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF] and bounded treewidth graphs [START_REF] Bonamy | Recoloring graphs via tree decompositions[END_REF][START_REF] Feghali | Paths between colourings of sparse graphs[END_REF].

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) ∪ {v}. Given a set X, we denote by N (X), the set (∪ v∈X N (v)) \ 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 +∞ if no such path exists), and it is denoted by d(u, v). Let r ∈ 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 v and w 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 reconguration graph.

Let α 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 α X the coloring α restricted to the vertices of X. We say that two colorings α and β agree on X if α X = β X .

We introduce two new notions that are essential in the paper: r-locally non-frozen colorings and r-safe graphs. Denition 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.

Denition 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 (∆ + 1)-colorings in the paper, we will say that G is r-safe if the (∆ + 1)-colorings of G are r-safe. Before we dene yet another notion, let us make a remark.

Remark 2.3. Consider a non-frozen vertex u in a ∆+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 ∆ + 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. Denition 2.4. Given an induced path P where the rst 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 rst between v and w, the nal 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 rst step is slightly dierent, but the second step is the same for both results. The rst step consists in reaching a coloring where the vertices of a xed 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 ∆ 3, and let I be a maximal independent set at distance d 15 in G. Let σ be a coloring of G that is non-frozen. Then it is possible to transform σ into a coloring µ where I is non-frozen, with O(n) single vertex recolorings.

For Theorem 1.2 (distributed recoloring), the rst step corresponds to the following proposition, where we start from an r-locally non-frozen coloring. Note that even if k = ∆ + 1, a k -coloring with k = ∆ exists, by Brook's theorem. Indeed, since σ is non-frozen and ∆ 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 ∆ 3 and σ, η be two non-frozen kcolorings of G with k ∆ + 1. Then we can transform σ into η with a sequence of at most O(∆ c∆ n) single vertex recolorings, where c is a constant. Proof. By Proposition 3.1, we can transform σ (resp. η) into a coloring µ (resp. µ ) which is non-frozen on I by recoloring O(n) vertices in total.

Let γ be an arbitrary ∆-coloring of G. In order to build the recoloring sequence from µ to µ , we will build one from µ to γ, and one from γ to µ . By Proposition 3.4, there is a recoloring schedule from µ (resp. µ ) to γ recoloring at most ∆ O(∆) independent sets. This sequence recolors at most ∆ O(∆) times each vertex, which completes the proof.

The second theorem is about local reconguration, and we assume that the colorings are r-locally non-frozen. Theorem 1.2. Let G be a graph with ∆ 3, k ∈ N with k ∆ + 1. Let σ, η be two k-colorings of G which are r-locally non-frozen. There exists three constants c, c , c such that we can transform σ into η with a parallel schedule of length at most

O(k c∆ + ∆ c r) in O(∆ c + log * n + k) rounds if k ∆ + 2. O(∆ c + log 2 n • log 2 ∆ + k) rounds otherwise.
Proof. We rst compute an independent set at distance d = 28 in a distributed manner in time O(∆ 28 + log * n) rounds in the LOCAL model by [START_REF] Barenboim | Distributed (∆ + 1)-coloring in linear (in ∆) time[END_REF]. Then by pluggnig the result of Proposition 3.2 with d = 28, we can transform σ (resp. η) into a coloring µ (resp. µ ) such that all the vertices of I are non-frozen with a recoloring schedule of length O(r∆ 178 ) in O(∆ 122 + log * n + r) rounds.

Assume rst that k ∆ + 2. It is easy to transform µ into a coloring γ with k -1 colors in one round: for every vertex that has color ∆ + 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 µ into γ eciently, and nish this proof. Now, if k = ∆ + 1, we rst compute an arbitrary ∆-coloring, in time O(log 2 n log 2 ∆), using the algorithm of [START_REF] Ghaari | Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition[END_REF], and then use Proposition 3.4 twice (between µ and γ, and between µ and γ).

4

Safeness and consequences

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 7 and every graph G of maximum degree ∆ 3, G is r-safe.

Consider a graph G of maximum degree ∆ 3. Let σ be proper (∆ + 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 rst 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.

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 d(v, z) 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) 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. Lemma 4.3. Let P = v 0 , . . . , v r be a shortest path from v to w. If there is an index 2 i r -3 , such that σ(v i ) = σ(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 η 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 η, 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 η.

Amongst the indices 2 i r -3 such that σ(v i ) = σ(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 η.

Proof. Let c = σ(v i+3 ). Let us make a few remarks:

1. σ(v i+2 ) = c, because σ is a proper coloring, 2. σ(v i+1 ) = c, because v i+2 is frozen in σ.
More generally, none of the neighbors of v i+2 except v i+3 has color c.

3. σ(v i ) = c, because σ(v i ) = σ(v i+3 ) by assumption.
Now, by construction and by the properties of ladders, we have η(v j+1 ) = σ(v j ), for every vertex v j of the ladder, except v r = w. Transposing the remarks above about σ to η we get that:

1. η(v i+3 ) = c, 2. η(v i+2 ) = c
, and more generally, no neighbor of v i+2 has color c.

3. η(v i+1 ) = c.
Consequently, c does not appear in the closed neighborhood of v i+2 in η, which implies that v i+2 is non-frozen in η, as claimed. By Claim 4.4, v i+2 is non-frozen in η. We can make a new ladder in η 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.

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 , . . . , v r be a shortest path from v to w. By Lemma 4.1, all the vertices in P but the rst 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 σ(v i ) = i mod 3 for every i 2. We denote by η 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 η. Note that, for i 3, η(v i ) = (i -1) mod 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 σ, and no degree-2 vertex can be frozen in a ∆ + 1-coloring, with ∆ 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 7, d(v, z) d(v, v 5 ) + 1 r -1. Therefore, by Lemma 4.2, z is frozen in σ. We will use the following claim: Claim 4.5. If z is non-frozen in η, then a nice recoloring exists.

Proof. Indeed, from η, 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 denes a nice recoloring sequence.

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 σ, v 5 is its only neighbor colored with σ(v 5 ). In η, v 5 is recolored with a dierent color, which implies that z is no longer frozen in η. 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 σ. Since z is frozen in σ, it does not have two neighbors colored with the same color. Moreover, in η, the two neighbors of z in P have color c 1 = c 1 -1 mod 3 and c 2 = c 2 -1 mod 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 } = {c 1 , c 2 }. It follows that z is non-frozen in η, 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 i 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 σ(z) = σ(v i+1 ) = (i + 1) mod 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 = w.) Then P is a shortest path from v to w, and since σ(z) = (i + 1) mod 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 7, and if i = 4 or 5, then (i + 1) -3 2, thus in both cases the lemma applies. This concludes the proof, and proves Theorem 3.3.

Consequences of Theorem 3.3

The next lemma ensures that, in the centralized setting, we can obtain a 28-locally nonfrozen coloring. Proposition 3.1. Let G be a connected graph of maximum degree ∆ 3, and let I be a maximal independent set at distance d 15 in G. Let σ be a coloring of G that is non-frozen. Then it is possible to transform σ into a coloring µ 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 = i, i . Note that for any pair a, b ∈ I, B(a, 7) and B(b, 7) are disjoint, since d 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 ∈ A and j ∈ I \ A, such that d G (i, j) is minimum among the such pairs. If d(i, j) 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 ∈ A and j ∈ I \ A such that d(j, i) 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) 2d which gives a contradiction. Now, let us denote by T a spanning tree of H rooted in v. Let τ 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 rst vertex of τ 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 τ 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 denition, P has length at most 2d and does not intersect B(i , 7) for any i = 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 \ 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.

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

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 ∆ 3, and let I be a maximal independent set at distance d 15 in G. Let σ be a r-locally non-frozen coloring. Then it is possible to transform σ into a coloring µ where I is non-frozen, in O(d∆ 4d+10 + d log * n + r) rounds, and with a schedule of length O((r + d)d∆ 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: rst, 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) ∈ I, such that d G (a, b) p. The graph H has maximum degree ∆ H = O(∆ p ), thus we can compute a (∆ H + 1)-coloring of H in O(∆ H + log * (|H|)) rounds in H [1]. Therefore, we can compute such an auxiliary coloring of I in G in O(p∆ p + p log * n) rounds (in G).
Claim 4.8. We can reach a coloring such that in the nal 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∆ 2d+4 ) computed in O(d∆ 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 ∈ 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 ∈ 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 ∈ 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(∆ 2d+4 ). 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(∆ 6d+14 ) in O(d∆ 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 ∈ 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 \X u is adjacent to X u . If u is non-frozen, then we can unfreeze all the vertices of I ∩ X u : since d 15, we can proceed exactly like in the proof of Proposition 3.1. Note that, similarly to the previous proof, because of our denition 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) 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(∆ 2d+4 ) recoloring steps.

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∆ 6d+10 ). The total number of rounds is O(d∆ 4d+10 + d log * n + r) since we can reuse the same auxiliary coloring for all the iterations.

5

Recoloring locally non-frozen colorings

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

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 , . . . , v n of the vertices such that for every i n, the vertex v i has at most d neighbors in v i+1 , . . . , 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 \ B S . Then there exists a (∆-1)-degeneracy ordering of G consisting of O(r •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 (∆ -1)-degenerate because we have removed at least one vertex from a connected graph of maximum degree ∆. The degeneracy ordering of G will be built by rst splitting G into layers such that each vertex v in layer i has at most ∆ -1 neighbors in layers j i. Then we will split each layer into independent sets using the coloring c.

We dene 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 r + 2. All the vertices in the rst layer have a neighbor in B S and, for every i 2, all the vertices in layer i have at least one neighbor in layer (i -1). So the graph induced by the layers ∪ j i L j is (∆ -1)-degenerate (and all the vertices of L i have degree ∆ -1 in ∪ j 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 (∆ -1)-degeneracy ordering of G composed of O(r • 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.

List-coloring lemma

The following lemma is a list-coloring adaptation of a proof of Dyer et al. [START_REF] Dyer | Randomly coloring sparse random graphs with fewer colors than the maximum degree[END_REF] 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) ∈ L u . Let τ be an ordering of V (G). We denote by d + τ (u) (or d + (u), when τ is clear from context) the number of neighbors of u that appear after u in τ . We say that a set of lists is safe for τ if, for every vertex u, |L u | d + u + 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 reconguration step an a → b step. A recoloring schedule where all the steps are a → 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 dierent a → 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, τ be an ordering of G composed of t consecutive independent sets and, d = max v∈V d + τ (u). Consider a set of lists (L v ) v∈V safe for τ . Let σ, η be two k-colorings of G compatible with (L v ) v∈V .

There exists a recoloring sequence from σ to η with a restricted schedule of length at most k t+1 where k = | ∪ v∈V L v |. Moreover, this schedule can be found in O(r) rounds if the independent sets of τ are given.

Proof. Let I t , . . . , I 1 be the independent sets of the ordering τ . For every i t, we denote by G i the graph G[∪ j i I j ].

Let us prove by induction on i that we can recolor G i from σ G i to η 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 • (k -1) k 2 exists. Indeed, for every pair a = b, we create an a → b step where we recolor the vertices of I 1 colored a in σ and b in η from color a to color b. After all these steps, the coloring is η 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 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 → b step. For every c = a, b, we add a b → 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 ∩ 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 → b step without creating monochromatic edges in G i .

Finally, at the end of the reconguration sequence of G i-1 , we add k • (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)

• k i + k • (k -1) k i+1 from σ to η 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.

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 σ, η be two k-colorings of G with k d + 2. Assume that G has a degeneracy ordering composed of t consecutive independent sets. Then there exists a recoloring sequence from σ to η with a restricted schedule of size at most k t+1 in the LOCAL model.

Recoloring outside the balls

Let us now prove that we can obtain a coloring where the vertices agree on V \ 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 ∆ + 1 and r 10. Let G be a graph of maximum degree ∆ 3, and let σ, η be two r-locally non-frozen k-colorings of G. Let S be a maximal independent set at distance r 2r + 2.

Let G = G[V \ B S ] where B S = ∪ x∈S B(x, r).
Then there is a recoloring schedule of length k O(r k) from σ to η such that η G = η G .

Proof. The rst part of the recoloring sequence is a pre-processing step to ensure that every vertex v ∈ S is non-frozen. Since σ 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 ∈ S, we can repeat this argument for every v ∈ 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 σ, 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 R in G from σ G to η G in at most (∆ + 2) O(r∆) steps.

Let us now explain how we can extend the restricted schedule R of G to G, that is, avoid the conicts 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 → b step of 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 conict.

For each ball of radius r centered in u ∈ S, we rst identify the vertices of Y u = Y ∩ 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 dierent color, leaving u unfrozen, and without modifying the color of any other vertex in Y u . Since Y u contains at most ∆ r vertices, we can change the color of all the vertices of Y u with a schedule of length at most 2r • ∆ 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 R has length at most k O(r k) , the new schedule have length at most k O(r k) • 2r k k+2 = k O(r k) , which completes the proof.

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 ∆ + 1. Let σ and η be two k-colorings of a graph G which only dier on X ⊆ 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 \ X colored the same. Then there is a recoloring schedule from σ to η of length at most k O(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 σ that appear on neighbors outside X, that is on N (v) ∩ (V \ X). We assign to every vertex v of G[C] the list of colors [k] \ Z v . Note that since the total number of colors is k ∆ + 1, every vertex x ∈ 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 \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 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 σ.

Finally, by Lemma 5.3, there exists a recoloring sequence of G[C] from σ to η which recolors each vertex at most k O(diam(C)k) times. Since we can treat each connected component of X simultaneously (there is no edge between them), the conclusion follows. Now, by Lemma 5.5, we can recolor all the vertices of B with the target coloring η in such a way that every vertex of B is recolored at most ∆ O(∆r) times (since the diameter of B is at most the diameter of B plus 5). We then nally recolor, if needed, the two vertices recolored k in the second item of the construction of B with their real target color in η.

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.

  Proposition 3.2. Let G be a connected graph of maximum degree ∆ 3, and let I be a maximal independent set at distance d 15 in G. Let σ be a r-locally non-frozen coloring. Then it is possible to transform σ into a coloring µ where I is non-frozen, in O(d∆ 4d+10 + d log * n + r) rounds, and with a schedule of length O((r + d)d∆ 6d+10 ) in the LOCAL model. For every r 7 and every graph G of maximum degree ∆ 3, G isThe second step, that is common to both theorems, consists in reaching a xed coloring γ, and corresponds to the following proposition. Proposition 3.4. Let G be a graph with ∆ 3 and I be an independent set at distance 28.

	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.

r-safe. Let r, k, k ∈ N such that k < k, k ∆+1. Let µ, γ be two colorings, using respectively at most k and k colors, that are both non-frozen on I. There is a recoloring schedule from µ to γ of length at most (k )

O(∆)

. Moreover, such a recoloring schedule can be computed in O(∆) rounds in the LOCAL model.

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.

[START_REF] Bartier | Recolouring planar graphs of girth at least ve[END_REF] All along the paper, ∆(G), or ∆ when G is clear from context, will denote the maximum degree of G.

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 specic case of toroidal grids.

1

* This work was supported by ANR project GrR (ANR-18-CE40-0032)

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 ∆ 3 and I be an independent set at distance 28. Let r, k, k ∈ N such that k < k, k ∆+1. Let µ, γ be two colorings, using respectively at most k and k colors, that are both non-frozen on I. There is a recoloring schedule from µ to γ of length at most (k ) O(∆) . Moreover, such a recoloring schedule can be computed in O(∆) rounds in the LOCAL model.

Proof of Proposition 3.4. Let us x r = 7. Let I be a maximal independent set at distance r = 2r + 14. Let G = G \ B I where B I = ∪ x∈I B(x, r). By Lemma 5.4, there is a coloring η which agrees with η on G \ B I and a recoloring schedule from σ to η of length at most k O(kr) . To conclude, we only need to nd a recoloring sequence from η to η, that is to prove that we can recolor all the balls of B I with their target coloring η.

For every ball B v of radius r centered in v ∈ I, we will dene a set B v which contains B v , is included in B(v, r + 5), and that satises the conditions of Lemma 5.5. Since I is an independent set at distance 2r + 14, for every v, w ∈ I, the sets B v and B w will be at distance at least 4. Let B I = ∪ v∈I B v . Since the diameter of each ball B v for v ∈ 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 ∈ I denoted by B for simplicity.

If a vertex of B has two neighbors in V \ 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 \ B is colored with k in η , since it agrees with η, which is a k -coloring with k < k by assumption.

Let us consider a path v 1 , v 2 , . . . , v 6 of vertices such that v i is at distance i from B. For every i ∈ {3, 4, 5}, we can remark we can obtain a desired set B if one of the following holds:

If deg(v i ) < ∆, then we simply take B = B ∪ j i v i which contains a vertex of degree less than ∆.

If N (v i ) \ 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 η (the coloring is proper since color k was not used in η by assumption). Now, in this new coloring, B = B ∪ j i v i satises 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 i 5, N (v i ) \ v i-1 is a clique and that all the v i 's have degree at least ∆.

Let z be a vertex of N (v 3 ) distinct from v 2 and v 4 (which exists since ∆ 3). The vertex z is at distance at most 4 from B. Moreover, v 4 z is an edge (otherwise N (v 3 ) \ v 2 is not a clique). Since N (v 4 ) \ v 3 is a clique, zv 5 must also be an edge. But then N (v 5 ) \ 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.


M Moniez

R Ansari

F Habibi

Searching for Galactic hidden gas through interstellar scintillation

, providing a solution for the Galactic hidden matter problem. This gas should form transparent "clumpuscules" of ∼ 10 AU size, with a column density of 10 24-25 cm -2 , and a surface filling factor smaller than 1%. The OSER project (Optical Scintillation by Extraterrestrial Refractors) is proposed to search for scintillation of extra-galactic sources through these Galactic -disk or halo -transparent H 2 clouds. This project should allow one to detect (stochastic) transverse gradients of column density in cool Galactic molecular clouds of order of ∼ 3 × 10 -5 g/cm 2 /10 000 km. We present the expectations from a complete simulation of the interstellar scintillation process. Test observations have been obtained through known nebulae to probe the concept in a controlled situation; we show preliminary results from their analysis.

1 Introduction: The signature of transparent H 2 -He inhomogeneous clouds

Refraction through an inhomogeneous transparent cloud (hereafter called screen) distorts the wave-front of incident electromagnetic waves (Fig. 1) [START_REF] Moniez | [END_REF]. The amplitude in the observer's plane after propagation is described by the Huygens-Fresnel diffraction theory. For a point-like source, the intensity in the observer's plane is affected by interferences which, in the case of stochastic inhomogeneities, takes on the speckle aspect. At least 3 distance scales characterize this speckle:

• The diffusion radius R dif f of the screen, defined as the transverse separation for which the root mean square of the phase difference is 1 radian [7]. R dif f characterizes the cloud turbulence.

• The Fresnel radius

R F = λz 0 2π ∼ 2221 km λ 1µm 1 2 z 0 1 kpc 1 2 , ( 1
)
of order of 1000 km to 7000 km at λ = 1000 nm, for a screen distance z 0 between 125 pc (distance of the Bok globule B68) to 10 kpc (typical distance of a halo-clumpuscule). The Fresnel radius characterizes the diffraction process.

• The refraction radius

R ref = 2πR 2 F R dif f = λz 0 Rdif f ∼ 31, 000 km λ 1µm z 0 1 kpc R dif f 1000 km -1 , ( 2
)
size of the diffraction image in the observer's plane from a patch of R dif f in the screens plane.

In addition, long scale structure of the screen can induce local focusing/defocusing configurations that produce intensity variations. 2 Expectations from simulation: intensity modulation, time scale, color effects

After crossing an inhomogeneous cloud described by the Kolmogorov turbulence law (Fig. 1, right), the light from a monochromatic point source produces an illumination pattern on Earth made of speckles of size R dif f within larger structures of size R ref (see Fig. 3, up-left). The illumination pattern from a stellar source of radius r s is the convolution of the point-like intensity pattern with the projected intensity profile of the source (projected radius R S = r s × z 0 /z 1 ) (Fig. 3, up-center). In general, the small speckle is almost completely smoothed, and only the large structures of size R ref shows a significant modulation, that decreases when the ratio

R S R ref = r s R dif f λz 1 ∼ 2.25 r s R R dif f 1000 km λ 1µm -1 z 1 10 kpc -1
(3) increases (Fig. 2). For a cloud moving with a transverse velocity V T relative to the line of sight, this pattern sweeps across the Earth at the same speed, inducing intensity fluctuations with characteristic time scale

t ref (λ) = R ref V T ∼ 5.2 minutes λ 1µm z 0 1 kpc R dif f 1000 km -1 V T 100 km/s -1 . ( 4
)
We will assume that the scintillation is mainly due to this screen motion rather than to the pattern variation due to the cloud structure evolution, as it is the case in radioastronomy observations [START_REF] Lyne | Pulsar Astronomy[END_REF] (frozen screen approximation).

For the Galactic H 2 -He clouds we are interested in, R S /R ref ∼ (r s /R ) × (R dif f /1200 km) at λ = 500 nm, assuming that the scintillating star is in the Large Magellanic Cloud (LMC). Therefore, at optical wavelength, one expects a relatively high intensity modulation index (m = σ I / Ī > 1%) at time scale t ref > ∼ 2 minutes (if V T = 200km/s) for ordinary LMC stars (of radius R S = R ) as soon as R dif f < ∼ 6500 km. As R ref depends on λ, one expects a significant variation of the characteristic time scale t ref (λ) between the red side of the optical spectrum and the blue side. This property is probably the best signature of the scintillation as it indicates a propagation effect, incompatible with any type of intrinsic source variability.

Toward an experimental setup for searching hidden matter

The search for scintillation induced by transparent Galactic molecular clouds needs the capability to sample at the sub-minute scale the luminosity of LMC or SMC main sequence stars with a photometric precision better than 1%. This performance can be achieved using a two meter class telescope, with a high quantum efficiency detector and a short dead-time between exposures. Multi-wavelength detection capability is necessary to exploit the dependence of the characteristic time scale with the wavelength.

As mentioned in [8], gas clumpuscules would cover 1% of the sky surface if they fill the halo. Therefore, the probability for a star to be subject to a scintillation with a modulation index m > m threshold is τ scint = α×1%×β(m threshold ), where α is the fraction of halo made of gaseous objects and β(m threshold ) is the probability for the cloud to produce scintillation with m > m threshold . As m is related to R dif f and to the source distance and radius, the β function depends only on the R dif f distribution when the source is known. Considering the lack of knowledge on the clouds turbulence, and the exploratory aspect of this program, we need a wide field detector to monitor many main-sequence small stars.

Foreground effects, background to the signal: Conveniently, atmospheric intensity scintillation is negligible through a large telescope (m scint 1% for a > 1 m diameter telescope [4]). Any other atmospheric effect such as absorption variations at the minute scale (due to fast cirruses for example) should be easy to recognize as long as nearby stars are monitored together. Asterosismology, granularity of the stellar surface, spots or eruptions produce variations of very different amplitudes and time scales. A rare type of recurrent variable stars exhibit emission variations at the minute scale, but they could be identified from their spectrum.

Preliminary studies with the NTT

To test the concept, we searched for gas induced scintillation of stars located behind visible nebulae with the ESO-NTT. In two nights of June 2006 we got 4749 consecutive exposures of T exp = 10 s, taken with the infra-red SOFI detector in K s and J towards B68, cb131, Circinus and SMC. For a future search for transparent hidden matter, visible light -corresponding to the maximum stellar emission-would be more optimal. Through the cores of B68, cb131 and Circinus, gas column densities of ∼ 10 22 atoms/cm 2 induce an average phase delay of 250 × 2π at λ = 2.18 µ. According to our studies, a few percent scintillation signal is expected from stars smaller than the sun, if relative column density fluctuations of only ∼ 10 -3 occur within less than a few thousand kilometers (corresponding to R dif f < ∼ 2000 km). Such small relative fluctuations cannot induce significant absorption variations, and we will neglect them. The expected time scale of the scintillation is t ref > ∼ 5 minutes, assuming V T ∼ 20 km/s. We produced the light curves of 9599 stars with ∼ 2000 measurements, using the EROS software [2]. We searched for stochastic luminosity fluctuations on the 788 best measured stars (i.e. with photometric precision better than 10%). About 1/4 of them are located behind the cloud. After blind selection and identification of known artifacts (hot pixels, dead zones, bright egrets...), we found only 6 stars with significant variability (Fig. 3, down-right), all of six interestingly located near the Bok globule limit and none outside the globule (Fig. 3, up-right). Their status should be clarified with the analysis of their light curve time structure (to be done), but the confirmation of a scintillation signal would probably need complementary observations. Nevertheless we can already conclude that the signal we are searching for should not be overwhelmed by background. The next steps should be to further investigate the correlation between the variability and the estimated gas column density, and to study the chromaticity of the intensity fluctuations, that need simultaneous observations with different filters.

Conclusions and perspectives

The opportunity to search for scintillation results from the subtle coincidence between the lever arm of interference patterns due to hypothetic turbulent gas in the Milky-Way and the angular size of the stars. The hardware and software techniques required for such searches are available just now, and a light project could be operational within a few years. Alternatives under study are the use of the data from the LSST project and from the GAIA mission. If a scintillation indication is found, one will have to consider an ambitious project involving synchronized telescopes, a few thousand kilometers apart. Such a project would allow to temporally and spatially sample an interference pattern, unambiguously providing the refractive length scale R ref , the speed and the dynamics of the scattering medium.

Figure 1 :

 1 Figure 1: Illumination pattern from a point source (left) after crossing a stochastic phase screen (simulation with levels of grey)(up).

Figure 2 :

 2 Figure 2: Intensity modulation index m = σ I / Ī of a stellar light-curve as a function of R S /R ref .

Figure 3 :

 3 Figure 3: ; Left panels: Illumination map at λ = 2.18µ on Earth from a point source (up-left)-and from a K0V star (r s = 0.85R , M V = 5.9) at 8 kpc (right). The bottom maps are illuminations in K s wide band. The refracting cloud is assumed to be at 160 pc. The red scale represents 20, 000 km. Right panels: Position of the 6 most variable stars on a combined visible+IR image showing the cloud geometry (up) and one of their light-curves (down).