Daniel Gonçalves
email: daniel.goncalves@lirmm.fr

Mickaël Montassier
email: mickael.montassier@lirmm.fr

Alexandre Pinlou
email: alexandre.pinlou@lirmm.fr

Entropy compression method applied to graph colorings *

Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmović et al. on colorings, Esperet and Parreau developed a framework to prove upper bounds for several chromatic numbers (in particular acyclic chromatic index, star chromatic number and Thue chromatic number) using the so-called entropy compression method.

Inspired by this work, we propose a more general framework and a better analysis. This leads to improved upper bounds on chromatic numbers and indices. In particular, every graph with maximum degree ∆ has an acyclic chromatic number at most 3 2 ∆ 4 3 + O(∆). Also every planar graph with maximum degree ∆ has a facial Thue choice number at most ∆ + O(∆ 1 2 ) and facial Thue choice index at most 10.

Introduction

In the 70's, Lovász introduced the celebrated Lovász Local Lemma (LLL for short) to prove results on 3-chromatic hypergraphs [START_REF] Erdős | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF]. It is a powerful probabilistic method to prove the existence of combinatorial objects satisfying a set of constraints. Since then, this lemma has been used in many occasions. In particular, it is a very efficient tool in graph coloring to provide upper bounds on several chromatic numbers [START_REF] Alon | Nonrepetitive colorings of graphs[END_REF][START_REF] Alon | Acyclic edge colorings of graphs[END_REF][START_REF] Fertin | Star coloring of graphs[END_REF][START_REF] Greenhill | Bounds on the generalized acyclic chromatic numbers of bounded degree graphs[END_REF][START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF][START_REF] Havet | List colouring squares of planar graphs[END_REF][START_REF] Molloy | A bound on the strong chromatic index of a graph[END_REF][START_REF] Molloy | A bound on the total chromatic number[END_REF]. Recently Moser and Tardos [START_REF] Moser | A constructive proof of the general lovasz local lemma[END_REF] designed an algorithmic version of LLL by means of the so-called Entropy Compression Method. This method seems to be applicable whenever LLL is, with the benefits of providing tighter bounds. Using ideas of Moser and Tardos [START_REF] Moser | A constructive proof of the general lovasz local lemma[END_REF], Grytczuk et al. [START_REF] Grytczuk | New approach to nonrepetitive sequences[END_REF] proposed new approaches in the old field of nonrepetitive sequences. Inspired by these works, Dujmovik et al [START_REF] Dujmović | Nonrepetitive colouring via entropy compression[END_REF] gave a first application of the entropy compression method in the area of graph colorings (on Thue vertex coloring and some of its game variants). As the approach seems to be extendable to several graph coloring problems, Esperet and Parreau [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF] developed a general framework and applied it to acyclic edge-coloring, star vertexcoloring, Thue vertex-coloring, each time improving the best known upper bound or giving very short proofs of known bounds. In the continuity of these works, we provide a more general method and give new tools to improve the analysis. As application of that method, we obtain some new upper bounds on some invariants of graphs, such as acyclic choice number, facial Thue chromatic number/index, ... The paper is organized as follows. In Section 2, we present the method and apply it to acyclic vertex coloring. It will be the occasion of providing improved bounds (in terms of the maximum degree). Then, in Sections 3 and 4, we describe the general method and provide its analysis. Finally, Section 5 is dedicated to the applications of that method.

Acyclic coloring of graphs

A proper coloring of a graph is an assignment of colors to the vertices of the graph such that two adjacent vertices do not use the same color. A k-coloring of a graph G is a proper coloring of G using k colors ; a graph admitting a k-coloring is said to be k-colorable. An acyclic coloring of a graph G is a proper coloring of G such that G contains no bicolored cycles ; in other words, the graph induced by every two color classes is a forest. Let χ a (G), called the acyclic chromatic number, be the smallest integer k such that the graph G admits an acyclic k-coloring.

Acyclic coloring was introduced by Grünbaum [START_REF] Grünbaum | Acyclic colorings of planar graphs[END_REF]. In particular, he proved that if the maximum degree ∆ of G is at most 3, then χ a (G) ≤ 4. Acyclic coloring of graphs with small maximum degree has been extensively studied [START_REF] Burstein | Every 4-valent graph has an acyclic 5-colouring[END_REF][START_REF] Dieng | Acyclic coloring of graphs with maximum degree bounded[END_REF][START_REF] Fertin | Acyclic coloring of graphs of maximum degree five: nine colors are enough[END_REF][START_REF] Fiedorowicz | Acyclic 6-colouring of graphs with maximum degree 5 and small maximum average degree[END_REF][START_REF] Hocquard | Acyclic coloring of graphs with maximum degree six[END_REF][START_REF] Kostochka | Graphs with maximum degree 5 are acyclically 7-colorable[END_REF][START_REF] Yadav | Acyclic vertex coloring of graphs of maximum ∆[END_REF][START_REF] Yadav | Acyclic vertex coloring of graphs of maximum degree 6[END_REF][START_REF] Yadav | Acyclic vertex coloring of graphs of maximum degree 5[END_REF] and the current knowledge is that graphs with maximum degree ∆ ≤ 4, 5, and 6, respectively verify χ a (G) ≤ 5, 7, and 11 [START_REF] Burstein | Every 4-valent graph has an acyclic 5-colouring[END_REF][START_REF] Kostochka | Graphs with maximum degree 5 are acyclically 7-colorable[END_REF][START_REF] Hocquard | Acyclic coloring of graphs with maximum degree six[END_REF]. For higher values of the maximum degree, Kostochka and Stocker [START_REF] Kostochka | Graphs with maximum degree 5 are acyclically 7-colorable[END_REF] showed that χ a (G) ≤ 1 + (∆+1) 2 4

. Finally, for large values of the maximum degree, Alon, McDiarmid, and Reed [START_REF] Alon | Acyclic coloring of graphs[END_REF] used LLL to prove that every graph with maximum degree ∆ satisfies χ a (G) ≤ 50∆ 4/3 . Moreover they proved that there exist graphs with maximum degree ∆ for which χ a = Ω

∆ 4/3
(log ∆) 4/3 . Recently, the upper bound was improved to 6.59∆ 4 3 + 3.3∆ by Ndreca et al. [START_REF] Ndreca | Improved bounds on coloring of graphs[END_REF] and then to 2.835∆ 4 3 + ∆ by Sereni and Volec [START_REF] Sereni | A note on acyclic vertex-colorings[END_REF].

We improve this upper bound (for large ∆) by a constant factor.

Theorem 1 Every graph G with maximum degree ∆ ≥ 24 is such that χ a (G) < min 3 2 ∆ At the end of Section 2.2.1 (see Remark 9), we give a method to refine these upper bounds, improving on Kostochka and Stocker's bound as soon as ∆ ≥ 27.

Alon, McDiarmid, and Reed [START_REF] Alon | Acyclic coloring of graphs[END_REF] also considered the acyclic chromatic number of graphs having no copy of K 2,γ+1 (the complete bipartite graph with partite sets of size 2 and γ + 1) in which the two vertices in the first class are non-adjacent. Let K γ be the familly of such graphs. Such structure contains many cycles of length 4 and they are an obstruction to get an upper bound on the acyclic chromatic number linear in ∆. Again using LLL, they proved that every graph G ∈ K γ with maximum degree ∆ satisfies χ a (G) ≤ ⌈32 √ γ∆⌉. Using similar techniques as for Theorem 1, we obtain: Theorem 2 Let γ ≥ 1 be an integer and G ∈ K γ with maximum degree ∆. We have χ a (G)

≤ 1 + ∆ 1 + √ 2γ + 4 .
As it is simpler, let us start with the proof of Theorem 2 that will serve as an educational example of the entropy compression method.

Graphs with restrictions on K 2,γ+1 's

We prove Theorem 2 by contradiction. Suppose there exists a graph G ∈ K γ with maximum degree ∆ such that χ a (G) > 1 + ∆ 1 + √ 2γ + 4 . We define an algorithm that "tries" to acyclically color G with κ = 1 + ∆ 1 + √ 2γ + 4 colors. Define a total order ≺ on the vertices of G.

Algorithm ACYCLICCOLORINGGAMMA_G runs as follows. Let ϕ i be the partial coloring of G after i steps (at the end of the i th loop). At Step i, we first consider ϕ i-1 and we color the smallest uncolored vertex v with V [i] (line 6 of the algorithm). We then verify whether one of the following types bad events happens: Event 1: G contains a monochromatic edge vu for some u (line 8 of the algorithm) ; Event k: G contains a bicolored cycle of length 2k (v = u 1 , u 2 , . . . , u 2k ) (line 11 of the algorithm).

If such events happen, then we uncolor some vertices (including v) in order that none of the two previous events remains. Clearly, ϕ i is a partial acyclic coloring of G. Indeed, since Event 1 is avoided, ϕ i is a proper coloring and since Event 2 is avoided, ϕ i is acyclic.

Proof of Theorem 2. Let us first note that the function defined by Algorithm ACYCLICCOLOR-INGGAMMA_G is injective. This comes from the fact that from each output of the algorithm, one can determine the corresponding input by Lemma 3. Now we obtain a contradiction by showing that the number of possible outputs is strictly smaller than the number of possible inputs when t is chosen large enough. The number of possible inputs is exactly κ t while the number of possible outputs is o(κ t ), as it is at most (1+κ) n ×o(κ t ). Indeed, there are at most (1+κ) n possible partial κ-colorings of G and there are at most o(κ t ) possible records by Lemma 4. Therefore, assuming the existence of a counterexample G leads us to a contradiction. That concludes the proof of Theorem 2. ✷

Algorithm analysis

Recall that ϕ i denotes the partial acyclic coloring obtained after i steps. Let us denote by ϕ i ⊂ V (G) the set of vertices that are colored in ϕ i . Let also v i , R i and V i respectively denote the current vertex v of the i th step, the record R after i steps, and the input vector V restricted to its i first elements.

Observe that as ϕ i is a partial acyclic κ-coloring of G, and as G is not acyclically κ-colorable, we have that ϕ i V (G), and thus v i+1 is well defined. This also implies that R has t "Color" lines. Finally observe that R i corresponds to the lines of R before the (i + 1) th "Color" line.

Lemma 3 One can recover

V i from (ϕ i , R i ).
Proof. By induction on i. Trivially, V 0 (which is empty) can be recovered from (ϕ 0 , R 0 ). Consider now (ϕ i , R i ) and let us try to recover V i . It is thus sufficient to recover R i-1 , ϕ i-1 , and

V [i].
As observed before, to recover R i-1 from R i it is sufficient to consider the lines before the last (i.e. the i th ) "Color" line. Then reading R i-1 , one can easily recover ϕ i-1 and deduce v i . Note that in the i th step we wrote one or two lines in the record: exactly one "Color" line followed by either nothing, or one "Uncolor, neighbor" line, or one "Uncolor, 2k-cycle" line. Indeed there cannot be an "Uncolor, 2k-cycle" line following an "Uncolor, neighbor" line, as v would be uncolored by the algorithm before considering bicolored cycles passing through v. Let us consider these three cases separately.

• If

Step i was a color step alone, then

V [i] = ϕ i (v i ) and ϕ i-1 is obtained from ϕ i by uncoloring v i . • If the last line of R i is "Uncolor, neighbor u", then V [i] = ϕ i (u) and ϕ i-1 = ϕ i . • If the last line of R i is "Uncolor, 2k-cycle (u 1 , . . . , u 2k )", then V [i] = ϕ i (u 2k-1 )
and ϕ i-1 is obtained from ϕ i by coloring the vertices u j for 2 ≤ j ≤ 2k -2 (which were uncolored in ϕ i ), in such a way that ϕ i-1 (u j ) equals ϕ i (u 2k-1 ) if j ≡ 1 mod 2, or equals ϕ i (u 2k ) otherwise. Note that this is possible because in the i th loop, the algorithm uncolored neither u 2k-1 nor u 2k .

This concludes the proof of the lemma. ✷

Let us now bound the number of possible records.

Lemma 4

Algorithm ACYCLICCOLORINGGAMMA_G produces at most o(κ t ) distinct records R.

Proof. Since Algorithm ACYCLICCOLORINGGAMMA_G fails to color G, the record R has exactly t "Color" lines (i.e. the algorithm consumes the whole input vector). It contains also "Uncolor" lines of different types: "neighbor" (type 1), "4-cycle" (type 2), "6-cycle" (type 3), . . . "n-cycle" (type n 2 ). Let T = 1, 2, . . . , n 2 be the set of bad event types. Let denote s j the number of uncolored vertices when a bad event of type j occurs. Observe that:

• For every "Uncolor, neighbor" step, the algorithm uncolors 1 previously colored vertex.

Hence set s 1 = 1.

• For every "Uncolor, 2k-cycle" step, where the cycle has length 2k, the algorithm uncolors 2k -2 previously colored vertices. Hence set

s k = 2k -2 for 2 ≤ k ≤ ⌊n/2⌋.
To compute the total number of possible records, let us compute how many different entries, denoted C j , an "Uncolor" step of type j can produce in the record. Observe that:

• An "Uncolor, neighbor" line can produce ∆ different entries in the record, according to the neighbor of v (the vertex just colored by the algorithm) that shares the same color. Hence set C 1 = ∆.

S(u):

The α∆

4 3 highest elements according to ≺ u ≺ u u N(u) N 2 (u) N (u ) ∩ N (v ) v Figure 1: Example of a special couple (u, v).
• An "Uncolor, 2k-cycle" line involving a cycle of length 2k can produce as many different entries in the record as the number of 2k-cycles going through v. Thus this number of entries is at most 1 2 γ∆ 2k-2 according to Lemma 3.2 of [START_REF] Alon | Acyclic coloring of graphs[END_REF]. Hence set

C k = 1 2 γ∆ 2k-2 for 2 ≤ k ≤ ⌊n/2⌋.
We complete the proof by means of Theorem 18 of Section 4 (see on page 18). Theorem 18 applies on Algorithm COLORING_G which is a generic version of Algorithm ACYCLICCOLOR-INGGAMMA_G. Consequently, let us consider the following polynomial Q(x):

Q(x) = 1 + i∈T C i x si = 1 + ∆x + 2≤i≤ n 2 1 2 γ∆ 2i-2 x 2i-2 < 1 + ∆x + γ∆ 2 x 2 2 -2∆ 2 x 2 for x < 1 ∆ Setting X = 1 ∆ 2 γ+2
, we have:

Q(X) X < ∆ γ + 2 2 1 + 2 γ + 2 + 1 = ∆ 1 + 2γ + 4 ≤ κ
Since γ ≥ 1, then 2 γ+2 < 1 and thus we have 0 < X < 1 ∆ ≤ 1. Therefore, Algorithm ACYCLICCOLORINGGAMMA_G produces at most o(κ t ) different records by Theorem 18. This completes the proof. ✷

Graphs with maximum degree ∆

To prove Theorem 1, we prove that, given a graph G with maximum degree ∆, we have χ a (G) <

3 2 ∆ 4 3 + 5∆ -14 for ∆ ≥ 24 in Section 2.2.1 and that χ a (G) < 3 2 ∆ 4 3 + ∆ + 8∆ 4 3 ∆ 2 3 -4 + 1 for ∆ ≥ 9 in Section 2.2.2.
The proof is made by contradiction. Suppose there exists a graph G with maximum degree ∆ which is a counterexample to Theorem 1. Define a total order ≺ on the vertices of G. Let N (u) and N 2 (u) be respectively the set of neighbors and distance-two vertices of u. For each pair of non-adjacent vertices u and v, let

N (u, v) = N (u) ∩ N (v), and let deg(u, v) = |N (u, v)|. For each vertex u of G, let the order ≺ u on N 2 (u) be such that v ≺ u w if deg(u, v) < deg(u, w), or if deg(u, v) = deg(u, w) but v ≺ w. A couple of vertices (u, v) with v ∈ N 2 (u) is special if there are less than α∆ 4 3
(α is a constant to be set later) vertices w such that v ≺ u w. That is, (u, v) is special if and only if, v is in the α∆ 4/3 highest elements of ≺ u (see Figure 1). Note that the couple (u, v) may be special while the couple (v, u) may be non-special. Let us denote S(u) ⊆ N 2 (u) the set of

vertices v such that (u, v) is special. By definition, |S(u)| = min α∆ 4 3 , |N 2 (u)| .

Algorithm 2: ACYCLICCOLORING_G

Input : V (vector of length t). Output: (ϕ, R).

1 for all v in V (G) do 2 ϕ(v) ← • 3 R ← newf ile() 4 for i ← 1 to t do 5 Let v be the smallest (w.r.t. ≺) uncolored vertex of G 6 ϕ(v) ← V [i] 7 Write "Color \n" in R 8 if ϕ(v) = ϕ(u) for u ∈ N (v) then // Proper coloring issue 9 ϕ(v) ← • 10 Write "Uncolor, neighbor u \n" in R 11 else if ϕ(v) = ϕ(u) for u ∈ S(v) then // Special couple issue 12 ϕ(v) ← • 13 Write "Uncolor, special u \n" in R 14 else if v belongs to a bicolored cycle of length 4 (v = u 1 , u 2 , u 3 , u 4 ) then // Bicolored cycle issue 15 ϕ(v) ← • 16 ϕ(u 2 ) ← • 17 Write "Uncolor, cycle (u 1 , u 2 , u 3 , u 4 ) \n" in R 18 else if v belongs to a bicolored path of length 6 (u 1 , u 2 = v, u 3 , u 4 , u 5 , u 6 ) with u 1 ≺ u 3 then // Bicolored path issue 19 ϕ(u 1 ) ← • 20 ϕ(v) ← • 21 ϕ(u 3 ) ← • 22 ϕ(u 4 ) ← • 23 Write "Uncolor, path (u 1 , u 2 , u 3 , u 4 , u 5 , u 6 ) \n" in R 24 return (ϕ, R)

First upper bound

By contradiction hypothesis, χ a (G) ≥ 3 2 ∆ 4 3 + 5∆ -14. Let κ be the unique integer such that

3 2 ∆ 4 3 + 5∆ -15 ≤ κ < 3 2 ∆ 4 3 + 5∆ -14 (i.e. κ = 3 2 ∆ 4 3 + 5∆ -15 ).

The algorithm

Let V ∈ {1, 2, . . . , κ} t be a vector of length t. Algorithm ACYCLICCOLORING_G (see below) takes the vector V as input and returns a partial acyclic coloring ϕ : V (G) → {•, 1, 2, . . . , κ} of G (recall that • means that the vertex is uncolored) and a record R.

Algorithm ACYCLICCOLORING_G runs as follows. Let ϕ i be the partial coloring of G after i steps (at the end of the i th loop). At Step i, we first consider ϕ i-1 and we color the smallest uncolored vertex v with V [i] (line 6 of the algorithm). We then verify whether one of the following types of bad events happens:

Event N (for neighbor): G contains a monochromatic edge vu for some u (line 8 of the algorithm);

Event S (for special): G contains a special couple (v, u) with u and v having the same color (line 11 of the algorithm);

Event C (for cycle): G contains a bicolored cycle of length 4 (v = u 1 , u 2 , u 3 , u 4 ) (line 14 of the algorithm);

Event P (for path): G contains a bicolored path of length 6 (u 1 , u 2 = v, u 3 , u 4 , u 5 , u 6 ) with u 1 ≺ u 3 (line 18 of the algorithm).

If such events happen, then we modify the coloring (i.e. we uncolor some vertices as mentioned in Algorithm ACYCLICCOLORING_G) in order that none of the four previous events remains. Note that at some Step i, for u and v two vertices of G such that (u, v) is a special couple but (v, u) is not, we may have ϕ(u) = ϕ(v); this means that u has been colored before v. Clearly, ϕ i is a partial acyclic coloring of G. Indeed, since Event 1 is avoided, ϕ i is a proper coloring ; since Events 3 and 4 are avoided, ϕ i is acyclic.

Proof of Theorem 1. As in the proof of Theorem 2, we prove that the function defined by ACYCLIC-COLORING_G is injective (see Lemma 5). A contradiction is then obtained by showing that the number of possible outputs is strictly smaller than the number of possible inputs when t is chosen large enough compared to n. The number of possible inputs is exactly κ t while the number of possible outputs is o(κ t ), as the number of possible (1 + κ)-colorings of G is (1 + κ) n and the number of possible records is o(κ t ) (see Lemma 6). ✷

Algorithm analysis

Recall that ϕ i , v i , R i , and V i respectively denote the partial acyclic coloring obtained after i steps, the current vertex v of the i th step, the record R after i steps, and the input vector V restricted to its i first elements.

We first show that the function defined by ACYCLICCOLORING_G is injective.

Lemma 5 V i can be recovered from (ϕ i , R i ).

Proof. First note that, at each step of Algorithm ACYCLICCOLORING_G, a "Color" line possibly followed by an "Uncolor" line is appended to R. We will say that a step which only appends a "Color" line is a color step, and a step which appends a "Color" line followed by an "Uncolor" line is an uncolor step. Therefore, by looking at the last line of R, we know whether the last step was a color step or an uncolor step.

We first prove by induction on i that R i uniquely determines the set of colored vertices at Step i (i.e. ϕ i ). Observe that R 1 necessarily contains only one line which is "Color"; then v 1 is the unique colored vertex. Assume now that i ≥ 2. By induction hypothesis, R i-1 (obtained from R i by removing the last line if Step i was a color step or by removing the two last lines if Step i was an uncolor step) uniquely determines the set of colored vertices at Step i -1. Then at Step i, the smallest uncolored vertex of G is colored. If one of Events 1 to 4 happens, then the last line of R i is an "Uncolor" line whose indicates which vertices are uncolored. Therefore, R i uniquely determines the set of colored vertices at Step i.

Let us now prove by induction that the pair (ϕ i , R i ) permits to recover V i . At Step 1, (ϕ 1 , R 1 ) clearly permits to recover V 1 : indeed, v 1 is the unique colored vertex and thus V [1] = ϕ 1 (v 1 ). Assume now that i ≥ 2. The record R i-1 gives us the set of colored vertices at Step i -1, and thus we know what is the smallest uncolored vertex v at the beginning of Step i. Consider the following two cases:

• If Step i was a color step, then ϕ i-1 is obtained from ϕ i in such a way that ϕ i-1 (u) = ϕ i (u)
for all u = v and ϕ i-1 (v) = •. By induction hypothesis, (ϕ i-1 , R i-1 ) permits to recover V i-1 and V [i] = ϕ i (v).

• If

Step i was an uncolor step, then the last line of R i allows us to determine the set of uncolored vertices at Step i and therefore, we can deduce ϕ i-1 . Then by induction hypothesis, (ϕ i-1 , R i-1 ) permits to recover V i-1 . We obtain V [i] by considering the following cases:

-If the last line is of the form "Uncolor, neighbor u", then

V [i] = ϕ i (u).
-If the last line is of the form "Uncolor, special u", then

V [i] = ϕ i (u).
-If the last line is of the form "Uncolor, cycle (u 1 , u 2 , u 3 , u 4 )", then

V [i] = ϕ i (u 3 ).
-If the last line is of the form "Uncolor, path (u 1 , u 2 , u 3 , u 4 , u 5 , u 6 )", then

V [i] = ϕ i (u 6 ).
This completes the proof. ✷ Lemma 6 Algorithm ACYCLICCOLORING_G produces at most o(κ t ) distinct records.

Proof. As Algorithm ACYCLICCOLORING_G fails to color G, the record R has exactly t "Color" steps. It contains also "Uncolor" lines of different types: "neighbor" (type N ), "special" (type S), "cycle" (type C), and "path" (type P ). Let T = {N, S, C, P } be the set of bad event types. Let denote s j the number of uncolored vertices when a bad event of type j occurs. Note that each "Uncolor" step of type "neighbor" (resp. "special", "cycle", and "path") uncolors 1 (resp. 1, 2, 4) previously colored vertex. Hence set s N = 1, s S = 1, s C = 2 and s P = 4.

To compute the total number of possible records, let us compute how many different entries, denoted C j , an "Uncolor" step of type j can produce in the record. By considering vertex v in ACYCLICCOLORING_G, observe that:

• An "Uncolor" step of type "neighbor" can produce ∆ different entries in the record, according to the neighbor of v that shares the same color; hence let C N = ∆.

• An "Uncolor" step of type "special" can produce |S(v)| ≤ α∆ 4 3 different entries in the record, according to the vertex u ∈ S(v) that shares the same color; hence let C S = α∆ • An "Uncolor" step of type "cycle" can produce as many different entries in the record as the number of 4-cycles going through v and avoiding S(v). We do not consider bicolored 4-cycles going through v and some vertex u ∈ S(v), since we would have an "Uncolor, special u" step instead. Hence this number of entries is bounded by ∆ Proof. There are at most ∆ 2 edges between N (v) and N 2 (v). Let d be an integer such that deg(v, u) ≥ d if and only if u ∈ S(v). Therefore, there are at least d|S(v)| edges between N (v) and S(v). Thus there are at most ∆ 2 -dα∆ 4 3 edges between N (v) and S(v) = N 2 (v) \ S(v), and

u∈S(v) deg(v, u) ≤ ∆ 2 -dα∆ 4 3 (1)
One can see that the set of induced 4-cycles passing through v and through some vertex u ∈ N 2 (v) is in bijection with the pairs of edges {ux, uy} with x = y and {x, y} ⊆ N (v, u). Thus there are deg(v,u) 2 such cycles. Summing over all vertices in S(v), we can thus conclude that this is less than the following value K = 1 2 u∈S(v) deg(v, u) 2 . As this function is quadratic in deg(v, u), and as here deg

(v, u) ≤ d, Equation (1) implies that K ≤ K(d) for K(d) = 1 2 (∆ 2 -dα∆ 4
3 )d. By simple calculation one can see that the polynomial

K(d) is maximal for d = ∆ 2 3
2α and we thus have that

K ≤ K ∆ 2 3 2α = ∆ 8 3
8α . This concludes the proof of the claim. ✷

• An "Uncolor" step of type "path" can produce as many different entries in the record as the number of 6-paths P = (u 1 , u 2 , u 3 , u 4 , u 5 , u 6 ) with u 2 = v and u 1 ≺ u 3 . Hence this number of entries is bounded by 1 2 ∆(∆ -1) 4 according to the next claim, and thus let

C P = 1 2 ∆(∆ -1) 4 .

Claim 8

Given a graph G with maximum degree ∆, for any vertex v of G, there are at most

1 2 ∆(∆ -1) 4 paths (u 1 , u 2 , u 3 , u 4 , u 5 , u 6 ) of length 6 with u 2 = v and u 1 ≺ u 3 .
Proof. Given vertex v, there are ∆ 2 possibilities to choose u 1 and u 3 , and then ∆ -1 candidates for being vertex u i+1 once u i is known (i ≥ 3). This clearly leads to the given upper bound. ✷

We complete the proof by means of Theoremm 18 of Section 4 (see on page 18). Let us consider the following polynomial Q(x):

Q(x) = 1 + i∈T C i x si = 1 + C N x sN + C S x sS + C C x sC + C P x sP = 1 + ∆x + α∆ 4 3 x + ∆ 8 3 8α x 2 + 1 2 ∆(∆ -1) 4 x 4 Setting X = 2 √ 2α ∆ 4 3
, we have:

Q(X) X = 1 √ 2α + α ∆ 4 3 + 8α 3 2 √ 2 + 1 ∆ -32α 3 2 √ 2 + 8α 3 2 √ 2 ∆ 6 - 4 ∆ + 1 ∆ 2 (2)
In order to minimize 1

√ 2α + α, we set α = 1 2 , giving X = 2 ∆ 4 3
and we obtain:

Q(X) X = 3 2 ∆ 4 3 + 5∆ -16 + 24 ∆ - 16 ∆ 2 + 4 ∆ 3 < 3 2 ∆ 4 3 + 5∆ -15 ≤ κ as soon as ∆ ≥ 24
Since 0 < X ≤ 1 for ∆ ≥ 24, Algorithm ACYCLICCOLORING_G produces at most o(κ t ) different records by Theorem 18. This completes the proof. ✷

Remark 9

For small values of ∆, note that setting α = 1 2 is not optimal. Indeed the best choice of α is the value minimizing the right term of Equation [START_REF] Alon | Acyclic coloring of graphs[END_REF]. For example, for ∆ = 27, setting α = 0.225 leads us to 194 colors instead of 242, already improving on Kostochka Output: (ϕ, R).

1 for all v in V (G) do 2 ϕ(v) ← • 3 R ← newf ile() 4 for i ← 1 to t do 5 Let v be the smallest (w.r.t. ≺) uncolored vertex of G 6 ϕ(v) ← V [i] 7 Write "Color \n" in R 8 if ϕ(v) = ϕ(u) for u ∈ N (v) then // Proper coloring issue 9 ϕ(v) ← • 10 Write "Uncolor, neighbor u \n" in R 11 else if ϕ(v) = ϕ(u) for u ∈ S(v) then // Special couple issue 12 ϕ(v) ← • 13 Write "Uncolor, special u \n" in R 14 else if v belongs to a bicolored cycle of length 2k (k ≥ 2), say (u 1 , u 2 = v, u 3 , . . . , u 2k ) with u 1 ≺ u 3 then // Bicolored cycle issue 15 for j ← 1 to 2k -2 do 16 ϕ(u j ) ← • 17 Write "Uncolor, cycle (u 1 , . . . , u 2k ) \n" in R 18 return (ϕ, R)

A better upper bound for large value of ∆

The choice of the bad event types is important and considering two different sets of bad event types (insuring the acyclic coloring property) may lead to different bounds. In the previous subsection, we have considered four bad event types that insure a coloring to be acyclic. In this subsection, we consider an other set of bad event types which leads to a better upper bound for large value of ∆.

Algorithm ACYCLICCOLORING-V2_G (see above) is a variant of Algorithm ACYCLICCOLOR-ING_G (see on page 6) based on the following set of three bad events:

Event N : G contains a monochromatic edge vu for some u (line 8 of the algorithm); Event S: G contains a special couple (v, u) with u and v having the same color (line 11 of the algorithm);

Event k: G contains a bicolored cycle of length 2k (u 1 , u 2 = v, u 3 , . . . , u 2k ) (line 14 of the algo- rithm);
This leads to the following upper bound when ∆ ≥ 9:

χ a (G) < 3 2 ∆ 4 3 + ∆ + 8∆ 4 3 ∆ 2 3 -4 + 1.
Let κ be the unique integer such that 3 2 ∆

4 3 +∆+ 8∆ 4 3 ∆ 2 3 -4 ≤ κ < 3 2 ∆ 4 3 +∆+ 8∆ 4 3 ∆ 2 3 -4
+1 and let α = 1 2 . We now briefly sketch the proof. Let T = N, S, 2, 3, 4, . . . , n 2 be the set of bad event types. Note that each "Uncolor" step of type "neighbor" (resp. "special" and "2k-cycle")) uncolors 1 (resp. 1, 2k -2) previously colored vertex. Hence set s N = 1, s S = 1 and s k = 2k -2.

By considering v in Algorithm ACYCLICCOLORING-V2_G, observe that:

• An "Uncolor" step of type "neighbor" can produce ∆ different entries in the record. Set C N = ∆.

• An "Uncolor" step of type "special" can produce

|S(v)| ≤ 1 2 ∆ 4 3
different entries in the record, according to the vertex u ∈ S(v) that shares the same color. Set

C S = 1 2 ∆ 4 3 .
• Now consider cycles of length 2k, k ≥ 2. For cycles of length 4, there are at most 1 4 ∆ 8 3

induced 4-cycles going through v and avoiding S(v) (see Claim 7); we set

C 2 = 1 4 ∆ 8 3 . Let k ≥ 3.
Let us upper bound the number of 2k-cycles going through v that may be bicolored. To do so, we count the number of 2k-cycles (u

1 , u 2 , u 3 , . . . , u 2k ) with u 2 = v, u 1 ≺ u 3 such that (u 1 , u 2k-1 ) or (u 2k-1 , u 1 ) is not special (if both (u 1 , u 2k-1
) and (u 2k-1 , u 1 ) are special, then u 1 and u 2k-1 cannot receive the same color). There are at most ∆ 2k-4 3 such cycles according to Claim 10. We set

C k = ∆ 2k-4 3 .
Claim 10 For k ≥ 3, there are at most

∆ 2k-4 3 2k-cycles (u 1 , u 2 , u 3 , . . . , u 2k ) going through v with v = u 2 and u 1 ≺ u 3 such that (u 1 , u 2k-1 ) or (u 2k-1 , u 1 ) is not special. Proof. As u 1 ≺ u 3 , given v, there are ∆ 2 possible (u 1 , u 3 ).
Then knowing u i , there are at most ∆ possible choices for u i+1 , 3 ≤ i ≤ 2k -2. Now let (r, s) be a non-special pair being either (u 1 , u 2k-1 ) or (u 2k-1 , u 1 ). Hence s ∈ N 2 (r)\S(r). Let d be the highest value of deg(r, u) for u ∈ N 2 (r)\S(r). Therefore, there are at least d|S(r)| edges between N (r) and S(r), and so at most

∆ 2 -d 2 ∆ 4 3 edges between N (r) and N 2 (r) \ S(r). It follows that d is at most 2∆ 2 3
. Hence, there are at most 2∆

Q(x) = 1 + i∈T C i x si = 1 + C N x sN + C S x sS + C 2 x s2 + ⌊n/2⌋ k≥3 C k x s k = 1 + ∆x + 1 2 ∆ 4 3 x + 1 4 ∆ 8 3 x 2 + ⌊n/2⌋ k≥3 ∆ 2k-4 3 x 2k-2 < 1 + ∆x + 1 2 ∆ 4 3 x + 1 4 ∆ 8 3 x 2 + ∆ 14 3 x 4 1 -∆ 2 x 2 for x < 1 ∆ Setting X = 2 ∆ 4 3
, we have X ≤ 1 ∆ as soon as ∆ ≥ 9 and thus:

Q(X) X < 3 2 ∆ 4 3 + ∆ + 8∆ 4 3 ∆ 2 3 -4 ≤ κ
Algorithm ACYCLICCOLORING-V2_G produces at most o(κ t ) different records by Theorem 18. This completes the sketch of the proof.

General method

In the previous section, we gave upper bounds on the acyclic chromatic number of some graph classes. To do so, we precisely analyzed the randomized procedure for a specific graph class and a Algorithm 4: COLORING_G Input : V = {1, 2, . . . , κ} t (vector of length t). Output: (ϕ, R).

1 for all v in V (G) do 2 ϕ(v) ← • 3 R ← newfile() 4 for i ← 1 to t do 5 v ← NextUncoloredElement(ϕ) 6 ϕ(v) ← V [i] 7 Write "Color \n" in R 8 if ϕ ∈ F(v) then 9 j ← BadEventType(v, ϕ) 10 k ← BadEventClass j (v, ϕ) 11 for ∀u ∈ UncolorSetBadEvent j (v, ϕ, k) do 12 ϕ(u) ← • 13
Write "Uncolor, Bad Event j, k \n" in R 14 return (ϕ, R) specific graph coloring. The aim of this section is to provide a general method that can be applied to several graph classes and many graph colorings (some applications of our general method are given in Section 5).

In the remaining of this section, G is an arbitrarily chosen graph. The aim of the general method is to prove the existence of a particular coloring of G using κ colors, for some κ. A partial coloring of G is a mapping ϕ : V (G) → {•, 1, 2, . . . , κ} (• means that the vertex is uncolored). We assume by contradiction that G does not admit such a coloring. In that case, we will show that Algorithm COLORING_G (see Algorithm 4) defines an injective mapping (Corollary 17) from κ t different inputs (for some t) to o(κ t ) different outputs (Theorem 18), a contradiction. Given a partial coloring ϕ, let ϕ denotes the set of vertices colored in ϕ.

Description of Algorithm COLORING_G

Given a vertex v of G, let F(v) denote the set of forbidden partial colorings anchored at v. This set is such that the vertex v is colored for any ϕ ∈ F(v). For example, Algorithm ACYCLICCOL-ORINGGAMMA_G (see Algorithm 1) is a special case of Algorithm COLORING_G, where, for any vertex v, the set F(v) consists of the partial colorings where v and one of its neighbor have the same color, or v belongs to a properly bicolored cycle.

A partial coloring ϕ of G is said to be allowed, if and only if, 1. either ϕ is empty (none of the vertices is colored), 2. or there exists a colored vertex v such that ϕ / ∈ F(v) and uncoloring v yields to an allowed coloring.

Algorithm COLORING_G constructs a partial coloring ϕ of G. A crucial invariant of Algorithm COLORING_G is that the partial coloring ϕ considered at the beginning of each iteration of the main loop is allowed.

At the beginning of each iteration, Algorithm COLORING_G starts with an allowed coloring ϕ and chooses an uncolored vertex v by NextUncoloredElement.

• NextUncoloredElement(ϕ): This function takes the set of colored vertices of G in ϕ as input and outputs an uncolored vertex (unless all vertices are colored).

Then Algorithm COLORING_G colors v using the next color from vector V . This new coloring ϕ either verifies ϕ / ∈ F(v) and consequently ϕ is allowed, or ϕ ∈ F(v) and in that case ϕ is an "almost" allowed coloring since uncoloring v yields an allowed coloring. Hence, let us define these forbidden colorings that can be produced by Algorithm COLORING_G.

A partial coloring ϕ of G is said to be a bad event anchored at v, if ϕ ∈ F(v) and if the partial coloring ϕ ′ , obtained from ϕ by uncoloring v, is such that

• ϕ ′ is an allowed coloring,
• v is the vertex output by NextUncoloredElement(ϕ ′ ).

We denote B(v) the set of bad events anchored at v. It is clear that B(v) ⊆ F(v). Hence, the colorings ϕ considered at line 8 of the algorithm are either allowed or belong to B(v). Therefore, the test at line 8 is thus equivalent to testing whether ϕ ∈ B(v).

Before going further into the description of COLORING_G, let us introduce the following refinements of the sets B(v). For some set T , each set B(v) is partitioned into | T | sets B j (v) where j ∈ T . We call the bad events of B j (v) the type j bad events. We now refine again each set B j (v). We partition each

B j (v) into different classes B k j (v)
where k belongs to some set C j (v) of cardinality at most C j , for some value C j (depending only on type j). The partition into classes must be sufficiently refined in order to allow some properties of the function RecoverBadEvent (see below).

After coloring v in the main loop, if the current coloring ϕ does not belong to B(v), then COL-ORING_G proceeds to the next iteration. Observe that in that case ϕ remains allowed as expected.

Suppose now that after coloring v, the current coloring ϕ belongs to B(v). In that case, COLOR-ING_G determines the values j and k such that ϕ ∈ B k j (v). That is done using the following two functions:

• BadEventType(v, ϕ): When ϕ is a bad event of B(v), this function outputs the element j ∈ T such that ϕ is a bad event belonging to B j (v).

• BadEventClass j (v, ϕ) for some j ∈ T : When ϕ is a bad event of B j (v), this function outputs the element k ∈ C j (v) such that ϕ is a bad event belonging to B k j (v).

Then COLORING_G uncolors the vertices given by UncolorSetBadEvent, and proceeds to the next iteration. A key property of UncolorSetBadEvent is to ensure that the obtained coloring (i.e. obtained after uncoloring the vertices given by UncolorSetBadEvent) is allowed as expected.

• UncolorSetBadEvent j (v, ϕ, k) for some j ∈ T : For any bad event ϕ of B k j (v) (with colored vertices ϕ), this function outputs a subset S of ϕ of size s j (for some value s j depending only on type j), such that uncoloring the vertices of S in ϕ yields an allowed coloring.

Often the property of leading to an allowed coloring is easy to fulfill (see Lemma 11). A set X of partial colorings of G is closed upward (resp. closed downward) if starting from any partial coloring of X, coloring (resp. uncoloring) any uncolored (resp. colored) vertex leads to another coloring of X.

Lemma 11

If every set F(u) is closed upward, then the set of allowed colorings is closed downward. Hence in that case, for any ϕ ∈ B(v), uncoloring a set S of vertices containing v, leads to an allowed coloring.

Proof. Let us first prove the first statement. Assume for contradiction that the set of allowed colorings is not closed downward, that is there exist an allowed coloring ϕ and a non-empty set S ⊂ ϕ, such that uncoloring the vertices in S leads to a non-allowed coloring ϕ ′ . As ϕ is allowed, there exists an ordering v 1 , . . . , v p , with p = |ϕ|, of the vertices in ϕ such that the restriction of ϕ to vertices v 1 , . . . , v i , denoted ϕ i , does not belong to F(v i ), for any i ≤ p. Let us denote ϕ ′ i the coloring obtained from ϕ i by uncoloring the vertices of S (if colored). As ϕ ′ is not allowed, there exists a value 1 ≤ j ≤ p such that ϕ ′ j ∈ F(v j ). But as F(v j ) is closed upwards, this contradicts the fact that ϕ j / ∈ F(v j ).

Consider now the second statement. For any ϕ ∈ B(v), uncoloring v leads to an allowed coloring (by definition of B(v)). Then the proof follows from the fact that allowed colorings are closed downward. ✷ Finally, to prove the injectivity of COLORING_G, we need that the following function exists.

• RecoverBadEvent j (v, X, k, ϕ ′ ) where X ⊆ V (G), k ∈ C j (v)
, and ϕ ′ is a partial coloring of G: The function outputs a bad event ϕ ∈ B k j (v), such that (1) ϕ = X and (2) uncoloring UncolorSetBadEvent j (v, ϕ, k) from ϕ one obtains ϕ ′ , if such partial coloring ϕ exists. Moreover, the partition into classes of B j (v) must be sufficiently refined so that at most one bad event ϕ fulfills these conditions.

Example

Let us illustrate our general method with the proofs of Section 2 on acyclic vertex-coloring. Observe that Algorithm 1 corresponds to Algorithm 4 for the following settings. For any vertex v, the set F(v) contains every partial coloring of G with a monochromatic edge or with a bicolored cycle involving v. Then one type (type 1) corresponds to monochromatic edges, and several types (type k, for k ≥ 2) correspond to bicolored cycles, one per possible length of the cycles. Then each type is partitionned into classes, each of them corresponding to one monochromatic edge or to one bicolored cycle, respectively. For the uncoloring process, one can notice that the number of uncolored vertices only depends on the type of bad events, s 1 = 1 and s k = 2k -2, and that the set of uncolored vertices only depend on the class (i.e. the monochromatic edge or the bicolored cycle). Furthermore, as the sets F(v) are closed upward and as the current vertex is always uncolored, at the end of each iteration the partial colorings are always allowed (by Lemma 11). Finally, as described in Subsection 2.1 there exists a function RecoverBadEvent j for each type of bad event j.

Similarly, Algorithm 2 also corresponds to Algorithm 4. Here, F(v) contains every partial coloring of G with a monochromatic edge vu, a monochromatic special pair (v, u), a properly bicolored 4-cycle (v, u 1 , u 2 , u 3 ) or a properly bicolored 6-path (u 1 , v, u 3 , u 4 , u 5 , u 6 ) with u 1 ≺ u 3 .

Algorithm COLORING_G and its analysis

From the previous subsection, we have that for j ∈ T , C j and s j respectively denote the number of type j bad event classes, and the number of vertices to be uncolored when a type j bad event occurs. We set

Q(x) = 1 + j∈T C j x sj
In this subsection, we prove the following:

Theorem [START_REF] Fertin | Acyclic coloring of graphs of maximum degree five: nine colors are enough[END_REF] The graph G admits an allowed κ-coloring for any integer κ such that

κ ≥ min 0<x≤1 Q(x) x .
Before going further to prove Theorem 12, let us state the two following remarks.

Remark 13

One can observe that the bound obtained when all s j = 1, namely κ ≥ 1 + j∈T C j , is the same as the one obtained by a simple greedy coloring. Indeed, while coloring the current vertex v, the bad events of type j "forbid" at most C j colors for v, and so 1 + j∈T C j colors suffice to color the graph greedily.

Remark 14

One can observe that the polynomial Q(x) only depends on the values

X k = j s.t. sj =k C j .
One could thus merge the bad event types having the same value s j .

From now on, we assume that G does not admit an allowed κ-coloring, this will lead to a contradiction. Let V ∈ {1, 2, . . . , κ} t be a vector of length t for some arbitrarily large t. The algorithm COLORING_G (see Algorithm 4) takes the vector V as input and returns an allowed partial coloring ϕ of G and a text file R (called the record). Let ϕ i , v i , R i , and V i respectively denote the partial coloring obtained by Algorithm COLORING_G after i steps, the current vertex v of the i th step, the record R after i steps, and the input vector V restricted to its i first elements. Note that the algorithm and especially the properties of UncolorSetBadEvent j (v, ϕ, k) ensure that each ϕ i is allowed. As ϕ i is an allowed partial κ-coloring of G and since G has no allowed κ-coloring by hypothesis, we have that ϕ i V (G) and that vertex v i+1 is well defined. This also implies that R has t "Color" lines. Finally note that R i corresponds to the lines of R before the (i + 1) th "Color" line.

Lemma 15 One can recover v i and ϕ i from R i .

Proof. By induction on i. Trivially, ϕ 0 = ∅ and v 0 does not exist. Consider now R i+1 and let us show that we can recover v i+1 and ϕ i+1 . To recover R i from R i+1 it is sufficient to consider the lines before the last (i.e. the (i + 1) th ) "Color" line. By induction hypothesis, one can recover

ϕ i from R i . Observe that v i+1 = NextUncoloredElement(ϕ i ). Let X = ϕ i + v i+1 .
If the last line of R i+1 is a "Color" line, then ϕ i+1 = X. Otherwise, the last line of R i+1 is an "Uncolor" line of the form "Uncolor, Bad Event j, k". Then, we have

ϕ i+1 = X \ UncolorSetBadEvent j (v i+1 , X, k). That completes the proof. ✷ Lemma 16 One can recover V i from (ϕ i , R i ).
Proof. By induction on i. Trivially, V 0 (which is empty) can be recovered from (ϕ 0 , R 0 ). Consider now (ϕ i+1 , R i+1 ) and let us try to recover V i+1 . By induction, it is thus sufficient to recover R i , ϕ i , and the value V [i + 1]. As previously seen in the proof of Lemma 15, we can deduce R i from R i+1 . By Lemma 15, we know ϕ i and we have v i+1 = NextUncoloredElement(ϕ i ). Note that in the (i + 1) th step of Algorithm COLORING_G, we wrote one or two lines in the record: exactly one "Color" line followed either by nothing, or by one "Uncolor, Bad Event j, k" line. Let us consider these two cases separately:

• If Step i + 1 was a color step alone, then V [i + 1] = ϕ i+1 (v i+1
) and ϕ i is obtained from ϕ i+1 by uncoloring v i+1 .

• If the last line of R i+1 is "Uncolor, Bad Event j, k", then the function RecoverBadEvent j (v i+1 , ϕ i , k, ϕ i+1 ) outputs the bad event ϕ ′ i that occured during this step of the algorithm. Then we have that

V [i + 1] = ϕ ′ i (v i+1
) and that ϕ i corresponds to the partial coloring obtained from ϕ ′ i by uncoloring v i+1 .

This concludes the proof of the lemma. ✷

Corollary 17

The mapping V → (ϕ, R) defined by Algorithm COLORING_G is injective.

Proof of Theorem 12. First observe that Algorithm COLORING_G can produce at most o(κ t ) distinct outputs (ϕ, R); indeed, there are at most (1 + κ) n partial colorings ϕ of G and at most o(κ t ) records R (by Theorem 18, see Section 4). This is less than the κ t possible inputs (for a sufficiently large t), and thus contradicts the injectivity of Algorithm COLORING_G (Corollary 17). This concludes the proof. ✷

Extension to list-coloring

Given a graph G and a list assignment L(v) of colors for every vertex v of G, we say that G admits a L-coloring if there is a vertex-coloring such that every vertex v receives its color from its own list L(v). A graph is k-choosable if it is L-colorable for any list assignment L such that |L(v)| ≥ k for every v. The minimum integer k such that G is k-choosable is called the choice number of G. The usual coloring is a particular case of L-coloring (all the lists are equal) and thus the choice number upper bounds the chromatic number. This notion naturally extends to edge-coloring and chromatic index.

Until now, our methods were developed for usual colorings (i.e. without lists). Every algorithm takes a vector of colors V as input and, at each Step i, a vertex v is colored with color V [i] (line 6 of Algorithm COLORING_G). It is easy to slightly modify our procedure to extend all our results to list-coloring. To do so, the input vector V is no longer a vector of colors but a vector of indices. Then, at each Step i, the current vertex v is colored with the V [i] th color of L(v). We then adapt the proof of Lemma 16 so that

V [i + 1] is no longer ϕ i+1 (v i+1 ) (or ϕ ′ i (v i+1 )) but instead it is the position of ϕ i+1 (v i+1 ) (or ϕ ′ i (v i+1 )) in L(v i+1 ).
Therefore, Theorems 1, 2, and 12 extend to list-coloring.

Bounding the number of records

The aim of this section is to prove one of our main theorems, namely Theorem 18, that upper bounds the number of possible records produced by Algorithm COLORING_G.

Let us define a class of records R which includes the records that Algorithm COLORING_G could produce in a real execution. In this section, let n = |V (G)| be the order of the graph G, T be a set of bad event types, and s j and C j be positive integers for all j ∈ T , corresponding to the number of uncolored vertices and the number of classes associated to the bad events of type j.

A record R ∈ R is a sequence of "Color" and "Uncolor, Bad Event j, k" lines, where j ∈ T and k ∈ {1, . . . , C j }. The Dyck paths are defined as staircase lattice paths on a square grid, from the lower-left corner to the upper-right corner, which do not go below the diagonal. We say that a Dyck path is partial when it does not end in the upper-right corner. The size of a (partial) Dyck path is its number of up-steps. Observe that a record R ∈ R can be seen as a partial Dyck path where

• each up-step corresponds to a "Color" line,

• each descent (maximal sequence of consecutive down-steps) of length ℓ is annotated with a couple (j, k) and corresponds to an "Uncolor, Bad Event j, k" line where ℓ = s j .

Observe Figure 2 which gives an example of such an annotated partial Dyck path where s j1 = 1, s j2 = 2, s j3 = 1, and s j4 = 2.

From now on, the term record refers to both a record produced by Algorithm COLORING_G and its corresponding annotated partial Dyck path.

At a given step, it is clear that the level of the record corresponds to the number of colored vertices in G (for example, at Step 8 of Figure 2, the graph G has 3 colored vertices). Thus the ending level of the record should be between 0 and n. Let us define the subclass B ⊆ R of the records ending at level 0. In the following, usual Dyck paths will be called non-partial Dyck path to emphasize the difference between Dyck paths and partial Dyck paths. Hence, B is the set of non-partial Dyck paths of R.

It is clear that the size of a record of R is the number of "Color" lines. Let r t (resp. b t ) be the number of records of size t in R (resp. B) for any t ≥ 0. We thus define the generating functions of R and B as R(y) = In practice, our aim is to minimize the value of Q(x)

x . Observe that:

Remark 19 In Theorem 18, the minimum value of Q(x) x is as follows:

• If s j = 1 for all j ∈ T , then the minimum is reached for x = 1 and

Q(x) x = 1 + j∈T C j .
• Otherwise, the minimum is reached for the unique positive root of the polynomial From now on, we consider the case where s j ≥ 2 for some j ∈ T . As observed by Esperet and Parreau [10, Lemma 6], there is a constant C (depending only on the lengths of the descents) that r t ≤ b t+C . It suffices hence to show that b t = o(λ t ). For that purpose we make use of the smooth implicit-function schema 1 (SIFS for short) of Meir and Moon [START_REF] Meir | On an asymptotic method in enumeration[END_REF] (see also Flajolet Thus B(y

P (x) = -1 + j∈T (s j -1)C j x
1 d ) = 1+ t≥1 b dt y t .
Hence A(y) = t≥0 a t y t with a 0 = 0 and a t = b dt for t ≥ 1. Thus A(y) is analytic at 0, a 0 = 0, and a t ≥ 0 for all t ≥ 0. Furthermore, note that for any sufficiently large t, the integer dt can be written as a sum which summands belong to {s j | j ∈ T }. Hence a t = b dt > 0 for any sufficiently large t > 0. It follows that A(y) is aperiodic 2 . By Equation (4), we have A(y) = G(y, A(y)) for the bivariate function G defined by

G(y, z) = j∈T C j y sj /d (z + 1) sj .
Observe that G(y, z) = j∈T 0≤i≤sj

s j i C j y sj /d z i ,
and hence G(y, z) is a bivariate power series satisfying the following conditions:

(a) G(y, z) is analytic in the domain |y| < +∞ and |z| < +∞.

(b) Setting G(y, z) = m,n≥0 g m,n y m z n , the coefficients of G satisfy g m,n ≥ 0, g 0,0 = 0, g 0,1 = 0, and g s j d ,sj > 0 for the j ∈ T such that s j ≥ 2.

(c) There exist two positive numbers r and s satisfying the system of equations3 G(r, s) = s and G z (r, s) = 1.

Indeed, by setting X = r 1/d (s + 1), these two equations respectively become j∈T C j X sj = s and j∈T s j C j X sj = s + 1.

By substracting the first one to the second one, we obtain that X is the unique positive root of P (x) (see Remark 19) which exists. The first equation hence clearly defines s. In this first equation adding 1 to both sides, and then multiplying them both by r 1/d , one obtains that r = (X/Q(X)) d .

Hence A(y) = t≥0 a t y t satisfies a smooth implicit-function schema with characteristic system (r, s), see Definition 33 of A. By Theorem 34, we have that a t = O t -3 2 r -t . It follows that

a t = o (r -t ) and b t = o r -t/d = o Q(X) X t
. As X is the unique positive root of P (x), this concludes the proof. ✷

Some applications of the method to graph coloring problems

In this section, we apply the framework described in Section 3 to different coloring problems. We improve several known upper bounds by at least an additive constant and sometimes also by a constant factor. More importantly, this framework allows simpler proofs with only few calculations. Indeed, directly using Theorem 12, one avoids the calculations made in Section 4.

Non-repetitive coloring

In a vertex (resp. edge) colored graph, a 2j-repetition is a path on 2j vertices (resp. edges) such that the sequence of colors of the first half is the same as the sequence of colors of the second half. A coloring with no 2j-repetition, for any j ≥ 1, is called non-repetitive. Let π(G) be the non-repetitive chromatic number of G, that is the minimum number of colors needed for any non-repetitive vertexcoloring of G. By extension, let π l (G) be the non-repetitive choice number of G. These notions were introduced by Alon et al. [START_REF] Alon | Nonrepetitive colorings of graphs[END_REF] inspired by the works on words of Thue [START_REF] Thue | Über unendliche zeichenreihen[END_REF]. See [START_REF] Grytczuk | Nonrepetitive colorings of graphs -a survey[END_REF] for a survey on these parameters. Dujmović et al. [START_REF] Dujmović | Nonrepetitive colouring via entropy compression[END_REF] proved that every graph G with maximum degree

∆ satisfies π l (G) ≤ 1 + 1 ∆ 1 3 -1 + 1 ∆ 1 3 ∆ 2 = ∆ 2 + 2∆ 5 3 + O(∆ 4
3 ) colors. However, their technique could provide tighter bounds from the second term on [24]. Here, we provide a simple and short proof of the following bound.

Theorem 20 Let G be a graph with maximum degree ∆ ≥ 3. We have:

π l (G) ≤ ∆ 2 + 3 2 2 3 ∆ 5 3 + 2 2 3 ∆ 5 3 ∆ 1 3 -2 1 3 = ∆ 2 + 3 2 2 3 ∆ 5 3 + O(∆ 4
3 ) (Note that 3

2 2 3 ≈ 1.89)
Proof. To do this, let us use the framework as follows. Let G be any graph with maximum degree ∆, and let n denote its number of vertices. In this application, the sets F(v) are closed upward. We directly proceed to the description of the bad events B(v) and the description of the required functions. Then, from the set B(v), we define the set F(v) as its upward closure.

• Let ≺ be any total order on the vertices of G. NextUncoloredElement(ϕ) returns the first uncolored vertex according to ≺.

• Let B(v) be the set of bad events ϕ anchored at v such that vertex v belongs to a repetition in ϕ. The set B(v) is partitioned into subsets B j (v), for 1 ≤ j ≤ n/2, in such a way that in every ϕ ∈ B j (v) the vertex v belongs to a 2j-repetition. Let C j (v) be the set of 2j-vertex paths going through v. Each set B j (v) is partitioned into subsets B P j (v) according to the path P ∈ C j (v) supporting the repetition. If in a bad event ϕ ∈ B(v) the vertex v belongs to several repetitions, then one of the repetitions is chosen arbitrarily to set the value j and the path P such that ϕ ∈ B P j (v). Let C j = j∆ 2j-1 as this upper bounds | C j (v)|. Indeed, there are ∆ 2j-1 possible paths on 2j vertices where v has a given position, and 2j possible positions for v, but in that case every path is counted twice.

Let us prove that any partial allowed coloring ϕ is a non-repetitive coloring. We proceed by induction on the number of colored of ϕ. If there is no colored vertex, then ϕ is clearly non-repetitive. Otherwise, there exists a colored vertex v such that ϕ ∈ F(v) and uncoloring v leads to a partial allowed coloring ϕ ′ . By induction, ϕ ′ is non-repetitive. Thus, if ϕ contains a repetition, then v is necessarily involved. In such a case, we would have ϕ ∈ F(v), a contradiction.

• The function UncolorSetBadEvent j (v, ϕ, P ) outputs the half of P containing v, and thus s j = j. By Lemma 11, this function fulfills all the requirements.

• Given P and the sequence of colors of one half of P (which is colored in ϕ ′ ), it is easy to recover the sequence of colors of the other half of P , and so RecoverBadEvent j (v, X, P, ϕ ′ ) is well-defined.

Consider now

Q(x) = 1 + 1≤j≤n/2 C j x sj = 1 + 1≤j≤n/2 j∆ 2j-1 x j < 1 + ∆x (∆ 2 x -1) 2 if x < 1 ∆ 2 By setting X = 1 ∆ 2 -2 ∆ 7 1 3 (X > 0 as ∆ ≥ 3), one obtains that Q(X) X < ∆ 2 + 3 2 2 3 ∆ 5 3 + 2 2 3 ∆ 5 3 ∆ 1 3 -2 1 3
By Theorem 12, G admits an allowed coloring (hence a non-repetitive coloring) with ⌈Q(X)/X⌉ colors. This concludes the proof of the theorem. ✷

An edge-coloring is called non-repetitive if, for every path with an even number of edges, the sequence of colors of the first half differs from the sequence of colors of the second half. The minimim number of colors needed to have such a coloring on the edges of G is called the Thue index of G, and is denoted by π ′ (G). By extension, let π ′ l (G) be the Thue choice index of G. Alon et al. [START_REF] Alon | Nonrepetitive colorings of graphs[END_REF] proved that every graph G with maximum degree ∆ satisfies π ′ (G) ≤ c∆ 2 with c = 2e 16 + 1. We can prove:

Theorem 21 Let G be a graph with maximum degree ∆ ≥ 3. Then

π ′ l (G) ≤ ∆ 2 + 2 4 3 ∆ 5 3 + O(∆ 4
3 ).

The only difference with the vertex case is that C j = 2j∆ 2j-1 .

Facial Thue vertex-coloring

We consider in this subsection a slight variation of non-repetitive coloring which applies to plane graphs (i.e. embedded planar graphs). Here the restriction on repetitions only applies on facial paths. More formally, consider a plane graph G. A facial path of G is a path on consecutive vertices on the boundary walk of some face of G. A vertex-coloring of G is said to be facially non-repetitive if none of the facial paths is a repetition. The notion can be extended to list coloring. Let π f (G) (resp. π f l (G)) denote the facial Thue chromatic number (resp. facial Thue choice number) that is the minimum integer k such that G is facially non-repetitively k-colorable (resp. k-choosable).

Barát and Czap [START_REF] Barát | Facial nonrepetitive vertex coloring of plane graphs[END_REF] proved that for any plane graph G, π f (G) ≤ 24. Whether the facial Thue choice number of plane graphs could be bounded from above by a constant is still an open question.

Recently Przybyło et al. [START_REF] Przybyło | On the facial Thue choice number of plane graphs via entropy compression method[END_REF] proved that, if G is a plane graph of maximum degree ∆, then π f l (G) ≤ 5∆, and asymptotically, π f l (G) ≤ (2 + o(1))∆. We improve these upper bounds as follows:

Theorem 22 Let G be a plane graph with maximum degree ∆ ≥ 2. Then,

π f l (G) ≤ ∆ + 4 √ ∆ + 3
Proof. Let G be a plane graph with maximum degree ∆. In this application, the sets F(v) are closed upward. We directly proceed to the description of the bad events B(v) and the description of the required functions. Then, from the set B(v), we define the set F(v) as its upward closure.

• As previously, let ≺ be any total order on the vertices of G. NextUncoloredElement(ϕ) returns the first uncolored vertex according to ≺.

• For 1 ≤ j ≤ ⌊n/2⌋ = p, let B j (v) be the set of bad events ϕ such that vertex v belongs to a repetition on a facial 2j-vertex path P . Let C j (v) be the set of facial 2j-vertex paths going through v. Each set B j (v) is partitioned into sets B P j (v), for every P ∈ C j (v), according to the path P supporting the repetition. The number of obtained classes is such that we set C 1 = ∆ and C j = 2j∆ for j ≥ 2. Indeed, there are at most ∆ possible faces for containing P , and 2j positions for v in P .

Let us prove that any partial allowed coloring ϕ is a facial non-repetitive coloring. Proceed by induction on the number of colored vertices of ϕ. Either ϕ has no colored vertex and it is facially non-repetitive, or there exists a colored vertex v such that ϕ ∈ F(v) and uncoloring v leads to a partial allowed coloring ϕ ′ , that is hence facial non-repetitive. Thus, if ϕ contains a facial repetition, then v is necessarily involved. In such a case, we would have ϕ ∈ F(v), a contradiction.

• The function UncolorSetBadEvent j (v, ϕ, P ) outputs the half of the path P containing v, and thus s j = j. By Lemma 11, this function fulfills all the requirements.

• Given P and the sequence of colors of the colored half of P , it is easy to recover the sequence of colors of the uncolored half of P , and so RecoverBadEvent j (v, X, P, ϕ ′ ) is well-defined.

Consider now

Q(x) = 1 + 1≤j≤n/2 C j x sj = 1 + ∆x + 2≤j≤p 2j∆x j < 1 + ∆x + 2∆x 2 2 -x (x -1) 2 for x < 1 By setting X = 1 2 √
∆ , and as ∆ ≥ 2 one obtains that

Q(X) X < ∆ + 4 √ ∆ + 3
By Theorem 12, G admits an allowed coloring (hence a facial non-repetitive coloring) with ⌈Q(X)/X⌉ colors. This concludes the proof of the theorem. ✷

Piotr Micek recently announced that this theorem can be improved asymptotically as for any plane graph G, π f l (G) ≤ O(log ∆) [24].

Facial Thue edge-coloring

Consider the facial Thue choice index π ′ f l (G) of a plane graph G, that is the minimum integer k such that G is facially non-repetitively edge k-choosable. Schreyer and Škrabul'áková [START_REF] Schreyer | On the facial Thue choice index of plane graphs[END_REF] proved that plane graphs have bounded facial Thue choice index, more precisely π ′ f l (G) ≤ 291. Recently Przybyło [START_REF] Przybyło | On the Facial Thue Choice Index via Entropy Compression[END_REF] improved that bound to 12. To obtain that upper bound with our framework, it is sufficient to consider as bad events the partial colorings having a facial 2j-repetition (for any j ≥ 1) with costs C j = 4j since an edge belongs to at most 4j facial 2j-edge paths.

Let us explain a way to improve that upper bound. The idea is that at each step the algorithm chooses the edge e to be colored in such a way that e is facially adjacent to an uncolored edge e ′ . Therefore, if at some step the algorithm colors such an edge e, then this edge belongs to at most 1 + 2j facial 2j-edge paths going through colored edges (one path in the face incident to e and e ′ and 2j paths on the other face incident to e). However, such an edge e does not always exist. For example if the algorithm has colored all the graph G but one edge, then this edge may belong to 4j colored facial 2j-edge paths. We manage to use this trick to obtain the improved bound of 10.

We will need the following definition. Given a plane graph G, its medial graph M (G) is defined as follows:

• its vertex set is the set of edges of G;

• there is an edge uv between the vertices u and v of M (G) if and only if the corresponding edges in G are facially adjacent (i.e. adjacent and both incident to the same face).

Theorem 23

For any plane graph G, any edge e * of G, and any assignment of lists of size 9, there exists a partial facial Thue edge-coloring of G where all the edges except e * are colored.

Proof. Let G be a plane graph with maximum degree ∆, and let e * be any edge of G. In this application, we want to ensure that at each iteration of the main loop the current edge to color is facially adjacent to (at least) one uncolored edge. This leads us to sets F(e) that are not closed upward. Hence they need to be described with care. For a given edge e, the set F(e) contains the partial colorings with a facial repetition involving e, and the partial colorings where the set of uncolored edges (i.e. vertices of M (G)), including e * , induces a disconnected graph in M (G).

Hence the set of allowed colorings is the set of partial colorings with no facial repetition, and where uncolored edges, including e * , induce a connected graph in M (G).

We conveniently define NextUncoloredElement in order to avoid bad events dealing with the case where uncolored edges induce a disconnected graph in M (G).

• For any set X ⊆ E(G) such that e * ∈ X, and such that M

(G)[X] is connected, the edge e = NextUncoloredElement(E(G) \ X) must be such that M (G)[X -e] is connected.
Hence, e may be chosen among leaves of a spanning tree of M (G)[X] rooted at e * .

Hence with that definition of NextUncoloredElement we have that for a given edge e, the set of bad events B(e) contains the partial colorings with a facial repetition involving e, where e is facially adjacent to an uncolored edge e ′ (its parent in the spanning tree described above, which might be e * ), and where the set of uncolored edges induces a connected graph in M (G). Let us introduce the bad event types and classes:

• For 1 ≤ j ≤ p = ⌊n/2⌋, let B j (e) be the set of bad events anchored at e such that e has an uncolored facially adjacent edge e ′ , and e belongs to a repetition on a (colored) facial 2j-edge path P .

The partition into classes is not obvious. Let e 1 , e 2 , e 3 and e 4 be the (at most four) edges of G facially adjacent to e, and let e ′ ∈ {e 1 , e 2 , e 3 , e 4 } be the uncolored one with smallest index.

Let us now partition B j (e) into sets B e ′ ,P j (e) according to the uncolored edge e ′ and the path P supporting the repetition. We have seen earlier that given an edge e ′ there are at most 1 + 2j possible paths P . As there are up to four possibilities for e ′ this partition has 4 + 8j parts, but the cases where e ′ has distinct values are independent. Let us hence merge these parts as follow. Let B k j (e), for 1 ≤ k ≤ 1 + 2j, be the union of B e1,P1 j (e), B e2,P2 j (e), B e3,P3 j (e) and B e4,P4 j (e), for some choice of paths P 1 , P 2 , P 3 and P 4 . The obtained partition has C j = 1+2j classes.

• Given the set of colored edges ϕ of some bad event ϕ ∈ B j (e), one can determine the facially adjacent uncolored edge e ′ . Hence given (also) the class k such that ϕ ∈ B k j (e), one can determine the path P supporting the repetition. The function UncolorSetBadEvent j (e, ϕ, k) outputs the half of the path P containing e, and thus s j = j. Note that as the edges of P are incident to the same face, and as e and e ′ are facially adjacent, uncoloring this set of edges leads to a partial coloring that has no repetition and such that the uncolored edges induce a connected graph in M (G), hence an allowed coloring (as required).

• Using again the fact that P can be retrived from ϕ (= X here) and k, one can easily design a function RecoverBadEvent j (v, X, k, ϕ i+1 ).

Consider now

Q(x) = 1 + 1≤j≤n/2 C j x sj = 1 + 1≤j≤n/2 (1 + 2j)x j < 1 1 -x + 2x (1 -x) 2 if x < 1 By setting X = √ 17-3 4
, one obtains that Q(X)/X < 9. Hence by Theorem 12, G admits a partial allowed 9-coloring (hence a partial facial Thue edge-coloring) where e * is the onlyuncolored edge. This concludes the proof of the theorem. ✷

Given Theorem 23, it seems likely that π ′ f l (G) ≤ 9 for any plane graph G. Actually one can show that it is the case if G has an edge e * incident to two faces of small sizes. Unfortunately we do not achieve this bound here, but we prove:

Corollary 24 For any plane graph G, π ′ f l (G) ≤ 10. Proof. For a given G, pick an arbitrary edge e * ∈ E(G) and an arbitrary color c ∈ L(e * ). For all the other edges of G, remove color c from their list. Now all these lists have size at least 9. By Theorem 23, it is possible to color all the edge of G except e * , avoiding facial repetitions. Then coloring e * with c cannot create any repetition, as c does not appear elsewhere in G. ✷ Remark 25 Note that in the proof of Theorem 23 we only use the fact that edges are adjacent to at most two faces, and thus it extends to any graph embedded on any surface. Hence, Theorem 23 and Corollary 24, both extend to arbitrary surface.

Generalised acyclic coloring

Let r ≥ 3 be an integer. An r-acyclic vertex-coloring is a proper vertex-coloring such that every cycle C uses at least min(|C|, r) colors. This generalisation of the notion of acyclic coloring (the r = 3 case) was introduced by Gerke et al. in the context of edge-coloring [START_REF] Gerke | The generalized acyclic edge chromatic number of random regular graphs[END_REF] and then by Greenhill and Pikhurko in the context of vertex-coloring [START_REF] Greenhill | Bounds on the generalized acyclic chromatic numbers of bounded degree graphs[END_REF]. Let A r (G) be the minimum number of colors in any r-acyclic vertex-coloring of G. By extension, let A l r (G) be the r-acyclic choice number of G. Greenhill and Pikhurko [START_REF] Greenhill | Bounds on the generalized acyclic chromatic numbers of bounded degree graphs[END_REF] proved in particular that, for r ≥ 4 and ∆ ≥ 3, every graph G with maximum degree ∆ satisfies A r (G) ≤ c∆ ⌊r/2⌋ where c = 2 (r+2)/3 r(r + 2). We reduce this constant factor as follows.

Theorem 26 Let G be a graph with maximum degree ∆ ≥ 3. For any r ≥ 4, we have that A l r (G) ≤ ∆ ⌊r/2⌋ + O ∆ (r+1)/3 .

In the following, all the defined events are strongly inspired by those defined by Greenhill and Pikhurko [START_REF] Greenhill | Bounds on the generalized acyclic chromatic numbers of bounded degree graphs[END_REF]. Let G be any graph with maximum degree ∆, and let n denote its number of vertices. Let ≺ be any total order on the vertices of G. NextUncoloredElement(ϕ) returns the first uncolored vertex according to ≺. In this application, the sets F(v) are closed upward. We hence use Lemma 11, to ensure that each function UncolorSetBadEvent fulfills all the requirements. We proceed now to the description of the bad events (the sets F(v) being deduced from B(v)), and the description of the required functions. We distinguish two cases according to r's parity.

Case r even

Set r = 2ℓ with ℓ ≥ 2. We consider the following sets of bad events anchored at vertex v:

• Let B 1 (v) be the set of bad events ϕ where "there exists a vertex u at distance at most ℓ (from v) having the same color as v". Let C 1 (v) be the set of vertices u at distance at most ℓ from v.

As | C 1 (v)| ≤ ℓ i=1 ∆(∆ -1) i-1 = ∆((∆-1) ℓ -1) ∆-2 ≤ ∆ ℓ we set C 1 = ∆ ℓ . Each set B 1 (v) is partitioned into classes B u 1 (v)
, for every vertex u ∈ C 1 (v), according to the vertex u that is colored like v. UncolorSetBadEvent 1 (v, ϕ, u) outputs the vertex v, and thus s 1 = 1. In addition, RecoverBadEvent 1 (v, X, u, ϕ ′ ) outputs the partial coloring ϕ obtained from ϕ ′ by coloring v with color ϕ ′ (u).

Here it is clear that an allowed coloring is a distance ℓ proper coloring. Furthermore, as r = 2ℓ, cycles C of length at most r + 1 will receive |C| distinct colors.

• Let B 2 (v) be the set of bad events ϕ where "v belongs to a path P on r + 2 vertices such that v and two other colored vertices, say a, b, have colors that already appear on P \{v, a, b}". (v) ⊂ B 2 (v) be the class of bad events ϕ where "both v and v ′ have the same color, both a and a ′ have the same color, and both b and b ′ have the same color". Let us count the number of such classes. First observe that v belongs to at most r+2 2 ∆(∆ -1) r paths on r + 2 vertices. Now observe that there are at most r + 2 possible choices for each vertex a, b, v ′ , a ′ , b ′ . Hence let us set C 2 = 1 2 (r + 2) 6 ∆ r+1 . UncolorSetBadEvent 2 (v, ϕ, (P, a, b, v ′ , a ′ , b ′ )) outputs the set {v, a, b}, and thus s 2 = 3. In addition, RecoverBadEvent 2 (v, X, (P, a, b, v ′ , a ′ , b ′ ), ϕ ′ ) outputs the partial coloring ϕ obtained from ϕ ′ by coloring vertices v, a and b respectively with colors ϕ ′ (v ′ ), ϕ ′ (a ′ ) and ϕ ′ (b ′ ).

These bad events imply that in an allowed coloring, cycles of length at least r + 2 contain at least r colors. Hence an allowed coloring is also a generalised r-acyclic coloring. Consider now

Q(x) = 1 + 1≤j≤n/2 C j x sj = 1 + C 1 x + C 2 x 3 By setting X = 1 2C2 1 3 one obtains that Q(X) X = C 1 + 3 2 2 3 C 1 3 2 = ∆ ℓ + 3 2 (r + 2) 2 ∆ (r+1)/3
By Theorem 12, G admits an allowed coloring (hence a generalised r-acyclic coloring) with ⌈Q(X)/X⌉ colors. This concludes the proof of the theorem for r even.

Case r odd

The odd case is similar to the even case. Let r = 2ℓ + 1 with ℓ ≥ 2. Let us use again the two types of bad events defined above. Now, type 1 bad events are sufficient to deal with cycles of length at most r. Type 2 bad events are still sufficient to deal with cycles of length at least r + 2. It remains to deal with cycles of length r + 1. Type 1 bad events forbid some kinds of length r + 1 cycles. As r + 1 = 2ℓ + 2, the cycles of length r + 1 that are not forbidden by type 1 bad events are those where each color appears only once, or where colors appearing several times, do it on antipodal vertices. We thus add two other bad event types to deal with this kind of cycles of length r + 1.

A pair of vertices {u, u ′ } is said to be special if u and u ′ are at distance exactly ℓ + 1 and if there exist at least ∆ ℓ+1 3

paths of length ℓ + 1 linking u and u ′ . Consider the two following new sets of bad events:

• Let B 3 (v) be the set of bad events ϕ where "there exists a special pair {v, u} such that v and u have the same color". Let C 3 (v) be the set of vertices u such that {v, u} is a special pair. Each set B 3 (v) is partitioned into classes B u 3 (v) according to the vertex u colored like v. As there are at most ∆ ℓ+1 paths of length ℓ + 1 starting from v, there exist at most ∆ One can check that these two new types of bad events handle the remaining cycles of length r + 1 colored with less than r colors. This ensures us that allowed colorings are generalised r-acyclic colorings. Consider now

Q(x) = 1 + 1≤j≤n/2 C j x sj = 1 + C 1 x + C 2 x 3 + C 3 x + C 4 x 2 By setting X = 1 ∆ (r+1)/3 one obtains that Q(X) X = ∆ ℓ + ∆ (r+1)/3 + ∆ (r+1)/3 1 + ℓ + 1 2 (r + 2) 6 = ∆ ℓ + ∆ (r+1)/3 2 + ℓ + 1 2 (r + 2) 6
By Theorem 12, G admits an allowed coloring (hence a generalised r-acyclic coloring) with ⌈Q(X)/X⌉ colors. This concludes the proof of the theorem for r odd.

Colorings with restrictions on pairs of color classes

For many graph colorings, the color classes are asked to induce independent sets while another property is asked to each pair of color classes. Aravind and Subramanian [START_REF] Aravind | Bounds on vertex colorings with restrictions on the union of color classes[END_REF] introduced a general definition that captures many known colorings. In their definition, restrictions may apply to any ℓ color classes, for any ℓ ≥ 2. Let us restrict ourselves to the case ℓ = 2.

Given a family F of connected bipartite graphs, a (2, F )-subgraph coloring of G is a proper coloring of V (G) such that the subgraph of G induced by any two color classes does not contain any isomorphic copy of H as a subgraph, for each H ∈ F . Denote by χ 2,F (G) the minimum number of colors used by any (2, F )-subgraph coloring of G. Denote by χ 2,F (∆) the maximum value of χ 2,F (G) for any graph G having maximum degree at most ∆. For example, when F is the family of even cycles, (2, F )-subgraph coloring is the usual acyclic vertex-coloring.

Using random graphs, Aravind and Subramanian [START_REF] Aravind | Bounds on vertex colorings with restrictions on the union of color classes[END_REF] showed the following lower bound on χ 2,F (∆).

Theorem 27 (Aravind and Subramanian [START_REF] Aravind | Bounds on vertex colorings with restrictions on the union of color classes[END_REF]) Given a connected bipartite graph H with m edges (m ≥ 2), we have

χ 2,{H} (∆) = Ω ∆ m m-1 (log ∆) 1/(m-1)
Hence, the same bound applies to χ 2,F (∆) for any family F containing a graph H with m edges.

The same authors later showed that this lower bound is almost tight. Let m ≥ 2 be an integer and let F be a family of connected bipartite graphs such that all the graphs have at least m edges. Theorem 29 We have

χ 2,F (∆) < (k ≤m v + 71)(m + 1)∆ m m-1 (5) χ 2,F (∆) < (k m e + 1 + o(1)) (m + 1)∆ m m-1 (6)
Proof. Let us use the framework described in Section 3 as follows. Let F = {H 1 , H 2 , . . .}. Let us also denote by n i and m i the number of vertices and edges in the forbidden graph H i for each i (recall m i ≥ m). For convenience, we introduce the value γ = m m-1 . Let G be any graph with maximum degree ∆, and let n denote its number of vertices. As in this application, the sets F(v) are closed upward we directly proceed to the description of the bad events (as F(v) is deduced from B(v)), and the description of the required functions.

• Let ≺ be any total order on the vertices of G. NextUncoloredElement(ϕ) returns the first uncolored vertex according to ≺.

• Let B E (v) be the set of bad events ϕ anchored at v such that vertex v belongs to a monochromatic edge uv (in ϕ).

Let C E (v) = N (v). Let us partition B E (v) into classes B u E (v) accord- ing to which edge uv is monochromatic in ϕ, for u ∈ C E (v). Clearly | C E (v)| ≤ ∆, thus let C E = ∆.
From here it is clear that an allowed coloring is proper.

• The function UncolorSetBadEvent E (v, ϕ, u) outputs the singleton {v} and thus s E = 1.

By Lemma 11, this function fulfills all the requirements.

• RecoverBadEvent E (v, X, u, ϕ ′ ) outputs the partial coloring ϕ ∈ B u E (v) obtained from ϕ ′ by coloring v with color ϕ ′ (u).

Following the approach of Aravind and Subramanian [START_REF] Aravind | Forbidden subgraph colorings and the oriented chromatic number[END_REF], we extend the notion of special pairs introduced by Alon et al. [START_REF] Alon | Acyclic coloring of graphs[END_REF] to bigger sets. For any j ≥ 2, a j-set S of G (i.e. a set of size j) is special if the set X = v∈S N (v) has size greater than ∆ j-γ(j-1) . Let us define the corresponding bad events.

• For 2 ≤ j < n, let B j•Set (v) be the set of bad events ϕ anchored at v such that vertex v belongs to a monochromatic special j-set S. Let C j•Set (v) be the set of special j-sets containing v. Let us partition B j•Set (v) into classes B S j•Set (v) according to which special j-set S ∈ C j•Set (v) is monochromatic. By Claim 30, the number of classes is at most 1 (j-1)! ∆ γ(j-1) = C j•Set .

Claim 30 Any vertex v of G belongs to less than 1 (j-1)! ∆ γ(j-1) special j-sets, for any j ≥ 2.

Proof. Observe that v belongs to ∆ ∆-1 j-1 stars (on j + 1 vertices) centered in N (v) having j -1 leaves in N 2 (v) (first choose a center and then j -1 of its neighbors). Now the j leaves of such a star are contained in at most one special j-set of v. On the other hand, a special j-set containing v covers more than ∆ j-γ(j-1) of these stars. Hence v belongs to less than ∆ ∆-1 j-1 × ∆ γ(j-1)-j < 1 (j-1)! ∆ γ(j-1) special j-sets. ✷

From here it is clear that in an allowed coloring there will be no monochromatic special j-set.

• For 2 ≤ j < n, let the function UncolorSetBadEvent j•Set (v, ϕ, S) outputs a (j -1)-subset of S containing v ; thus s j•Set = j -1. Again by Lemma 11, this function fulfills all the requirements.

• If RecoverBadEvent j (v, X, S, ϕ ′ ) is called, then there is only one vertex of S colored in ϕ ′ , say w. Hence RecoverBadEvent j (v, X, S, ϕ ′ ) outputs the partial coloring obtained from ϕ ′ by coloring all the vertices of S with ϕ ′ (w).

As proposed in [START_REF] Aravind | Forbidden subgraph colorings and the oriented chromatic number[END_REF], one bad event type can deal with all the graphs in F >m v ⊆ F the set of forbidden graphs having more than m vertices.

• Let B F >m v (v) be the set of bad events ϕ anchored at v such that vertex v belongs to a connected properly bicolored subgraph I on m + 1 vertices. Note that such subgraph I of G is not necessarily isomorphic to a graph of F >m v . However this type of bad events deal with all the graphs of F with at least m + 1 vertices. Let C F >m v (v) be the set of all connected bipartite graphs I on m + 1 vertices that contain vertex v. We partition

B F >m v (v) into classes B I F >m v (v)
according to the bicolored subgraph I. By the proof of Lemma 2.4 in [START_REF] Aravind | Bounds on vertex colorings with restrictions on the union of color classes[END_REF] we have that the number of classes,

| C F >m v (v)| ≤ (m + 1)4 m+1 ∆ m = C F >m v .
From here it is clear that in an allowed coloring there will be no properly bicolored copy of any H i ∈ F with more than m vertices. We define a new bad event type for each graph H i ∈ F ≤m v , that is each graph of F with at most m vertices. Let V 1 and V 2 be the two independent sets partitioning V (H i ).

• The function UncolorSetBadEvent

• Let B Hi (v) be the set of bad events ϕ anchored at v such that vertex v belongs to a properly 2-colored subgraph S isomorphic to H i ∈ F ≤m v , and such that S does not contain a monochromatic special j-set. Let C Hi (v) be the set of all subgraphs S isomorphic to H i , containing v, and without special j-set contained in one of the two parts of S. The set B Hi (v) is partitioned into classes B S Hi (v) according to the bicolored copy, S. By Claim 31 (see below), the number of classes is at most n i ∆ γ(ni-2)-m i -m m-1 = C Hi .

Claim 31 For any vertex v of G, v belongs to at most n i ∆ γ(ni-2)-m i -m m-1 copies of H i = (V 1 , V 2 , E) in G that do not contain any special set in the images of V 1 nor in the image of V 2 . (That is n i ∆ (γ)(ni-2) copies for m i = m and o(∆ γ(ni-2) ), otherwise.)

Proof. Let us consider only the copies of H i where v corresponds to a given vertex u of H i . Now orient H i acyclically so that u is the unique sink, and let us denote by u = u 1 , . . . , u ni the vertices of H i in such a way that for any 1 ≤ j ≤ n i the out-neighborhood of u j corresponds to its neighbors with index lower than j. Note that d + (u j ) ≥ 1 for all 1 < j ≤ n i , and that m i = 1<j≤ni d + (u j ).

Observe that once u 1 , . . . , u j-1 are set, there are at most ∆ d + (uj )-γ(d + (uj )-1) choices for u j . This comes from the fact that the out-neighborhood of u j is monochromatic and hence cannot be a special d + (u j )-set. This leads to the following bound on the number of such copies of H i . As there are n i possible choices for mapping v in H i , this concludes the claim. ✷

Now it is clear that an allowed coloring is a (2, H i )-subgraph coloring for any H i ∈ F . An allowed coloring is thus a (2, F )-subgraph coloring.

• UncolorSetBadEvent Hi (v, ϕ, S) outputs n i -2 vertices of S including v and such that the two remaining vertices, say v 1 and v 2 , are such that v j ∈ V j for j = 1, 2. Note that s Hi = n i -2. Again by Lemma 11, this function fulfills all the requirements.

• RecoverBadEvent Hi (v, X, S, ϕ ′ ) outputs the partial coloring obtained from ϕ ′ by properly extending the 2-coloring of the two colored vertices of S to the whole S. By Theorem 12, G admits an allowed coloring (hence a facial non-repetitive coloring) with ⌈Q(X)/X⌉ < (k m e + 1 + o( 1)) (m+1)∆ γ colors. This concludes the proof of the second statement of the theorem. ✷ Remark 32 For given instances of F , tighter bounds can be inferred with the general method. For example for star colorings of graphs, which correspond to (2, {P 4 })-subgraph coloring, it is not necessary to have bad events for special sets. It suffice to have one bad event ensuring that the coloring is proper (with C 1 = ∆ and s 1 = 1), and one bad event to avoid bicolored P 4 's (with C 2 = 2∆(∆ -1) 2 and s 2 = 2). This yields to the bound 2 √ 2∆ 3 2 + ∆ -√ 8∆ + 1 (by setting X = 1/( √ 2∆(∆ -1))), similar to the one in [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF].

Consider now

Q(x) = 1 + C E • x sE + 2≤j<n C j•Set • x sj•Set + C F >m v • x s F >m v + Hi∈F ≤m v C Hi • x sHi = 1 + ∆x +

Conclusion

One should note that the framework presented in Section 3 may, in some cases, benefit from some sophistication. The version we presented here seems to be a good compromise between efficiency and clarity for the applications we considered. We have seen in Subsection 5.3 how, at any step i, one can get benefit from ϕ i-1 to decrease the values C j . One could also take into account the order in which the vertices of ϕ i-1 have been colored. For example, if (u, v) is a special pair (as in Subsection 2.2) and u has been colored after v to obtain ϕ i-1 , then one could be sure that the colors of u and v are distinct. Thus one would not have to consider bad events where u and v are colored the same. One could thus imagine that all the functions presented in Subsection 3.1 could depend on the ordering π in which the vertices of ϕ i-1 were colored. Finally an interesting way of improving this framework would be handling algorithms where the costs of a given bad event may vary. For example, one can imagine that, for some vertices, a type j bad event costs C j , while for some other vertices the cost is C ′ j . A simple way to analyze this is to set the cost of each type j bad event to max{C j , C ′ j }. We wonder whether there exists a better approach.

http://arxiv.org/ps/1406.4380v2

8 3 8αClaim 7 3 8α induced 4 -

 83734 according to the next claim, and thus let C C = ∆ Given a graph G with maximum degree ∆, for any vertex v of G, there are at most ∆ 8 cycles going through v and avoiding S(v).

2 3

 2 possible choices for u 2k . This leads to the given upper bound. ✷Let us consider the following polynomial Q(x):

t≥0r

  t y t and B(y) = t≥0 b t y t . Theorem 18 Algorithm COLORING_G produces at most o Q(x) x t distinct records with t "Color" lines where Q(x) = 1 + j∈T C j x sj and for any x ∈]0, 1].

1 d

 1 and Sedgewick's book [15, Section VII.4.1]). Function B(y) does not satisfy the SIFS and we thus introduce the function A(y) defined by A(y) = B(y ) -1 where d = gcd{s j | j ∈ T }. We prove in the following that A(y) satisfies the SIFS. Note that the size of Dyck paths of B is multiple of d. Therefore, we have: B(y) = t≥0 b t y t = t multiple of d b t y t .

  Let us define a partition of B 2 (v). Consider the set C 2 (v) formed by all tuples (P, a, b, v ′ , a ′ , b ′ ) such that P is a path on r + 2 vertices containing vertices v, a, b, v ′ , a ′ , b ′ where |{v, a, b}| = 3, 1 ≤ |{v ′ , a ′ , b ′ }| ≤ 3 and {v, a, b} ∩ {v ′ , a ′ , b ′ } = ∅. Let B (P,a,b,v ′ ,a ′ ,b ′ ) 2

2 3 4 3 (ℓ+1) = ℓ∆ 2 3 1 3

 2421 (ℓ+1) = ∆ (r+1)/3 = C 3 such classes. Functions UncolorSetBadEvent 3 and RecoverBadEvent 3 are defined similarly to the first type of bad events, with s 3 = 1.• Let B 4 (v) be the set of bad events ϕ where "v belongs to a cycle C of length r + 1 = 2ℓ + 2 such that v and its antipodal vertex v ′ (on C) have the same color, are at distance ℓ + 1 from each other but do not form a special pair, and such that C contains another pair of antipodal vertices {u, u ′ } having the same color". Let C 4 (v) be the set of couples (C, u) such that C is a (r + 1)-cycle containing v and u as non-antipodal vertices. Each setB 4 (v) is partitioned into classes B (C,u) 4 (v), for every (C, u) ∈ C 4 (v). There exist at most ℓ∆ (r+1) = C 4 such classes. Indeed, there are ∆ ℓ+1 choices for vertex v ′ and the path from v to v ′ ; as v and v ′ do not form a special pair, there are ∆ (ℓ+1) choices for the path from v ′ back to v; and finally there are ℓ possibilities for the pair {u, u ′ } of antipodal vertices. The function UncolorSetBadEvent 4 (v, ϕ, (C, u)) outputs {v, u}, so s 4 = 2, and RecoverBadEvent 4 clearly exists.

Theorem 28 (- 1

 281 Aravind and Subramanian[START_REF] Aravind | Forbidden subgraph colorings and the oriented chromatic number[END_REF]) For some constant C depending only on F , we have χ 2,F (∆) ≤ C∆ m mPartition the graphs in F according to their number of vertices. Let F ≤m v (resp. F >m v ) denote the subset of F with graphs on at most m vertices (resp. more that m vertices). Let also k ≤m v = |F ≤m v |. We consider another parition of F according to the number of edges in each graph. Let F m e (resp. F >m e ) denote the subset of F with graphs on exactly m edges (resp. more that m edges); and let k m e = |F m e |. The constant C mentionned in Theorem 27 is either 64(m + 1) 3 k ≤m v or 128(m + 1) 3 according to whether k ≤m v > 0 or not. Following the approach of Aravind and Subramanian, we improve C as follows.

  F >m v (v, ϕ, I) outputs a (m -1)-subset of V (I) containing v (recall I is a properly bicolored subgraph on m+ 1 vertices), such that the two remaining vertices v 1 and v 2 are adjacent (and thus have distinct colors). Note that s F >m v = m-1. Again by Lemma 11, this function fulfills all the requirements.• If RecoverBadEvent F >m v (v, X, I, ϕ ′ ) is called, then there are only two adjacent vertices of I, v 1 and v 2 , colored in ϕ ′ . Hence RecoverBadEvent F >m v (v, X, I, ϕ ′ ) outputs the partial coloring obtained from ϕ ′ by properly extending the 2-coloring of v 1 and v 2 to the whole I.

1<j≤ni∆

  d + (uj )-γ(d + (uj )-1) ≤ ∆ mi-γ(mi-ni+1) ≤ ∆ (1-γ)mi+γ(ni-1)

1 + 2 < 1 1 m- 1 < 1 ( 2 ) 2 < 2 < 1 m- 1 + 1 <

 121111222111 x) j-1 + (m + 1)4 m+1 ∆ m x m-Hi∈F ≤m v n i ∆ γ(ni-2)-m i -m m-1 x ni-∆x + e ∆ γ x + 16(m + 1)(4∆ γ x) m-1 + Hi∈F ≤m v n i (∆ γ x) ni-2 ∆ -m i -m m-By setting X = 1 4∆ γ , as ∆ and as for H i ∈ F ≤m v we have 3 ≤ n i ≤ m, one obtains that By Theorem 12, G admits an allowed coloring (hence a (2, F )-subgraph coloring) with ⌈Q(X)/X⌉ < (k ≤m v+ 71)(m + 1)∆ γ colors. This concludes the proof of the first statement of the theorem. For the second statement we proceed similarly but there are two differences. (1) Recall the partition of F into F m e and F >m e according to the number of edges. We replace the set F >m e by the set T m+1 e of all trees on exactly m + 1 edges. As every graph in F >m e contains a (m + 1)-edge tree, a (2, F m e ∪ T m+1 e )-subgraph coloring is also a (2, F )-subgraph coloring. All the graphs F m e ∪ T m+1 e are treated similarly by assigning each of them a specific bad event.There is no more the bad event type F >m v . This yields to the following Q(x).Q(x) = 1 + C E • x sE + 2≤j<n C j•Set • x sj•Set + Hi∈F m e ∪T m+1e C Hi • x sHi ∆x + e ∆ γ x + ∆x + e ∆ γ x + By setting X = 1 ∆ γ and as 3 ≤ n i ≤ m i + 1, one obtains that Q(X) X < ∆ γ ∆ e + k m e (m + 1) + |T m+1 e ∆ γ (k m e (m + 1) + e + o(1))

Table 1 :

 1 Actually one can observe in Table1that the optimal value of α (for a Optimal values of α for some given ∆.

	and Stocker's

4

= 197.

Algorithm 3: ACYCLICCOLORING-V2_G

Input : V (vector of length t).

The smooth implicit-function schema is given in A.

Aperiodic is used in the usual sense of Definition IV.5 of Flajolet-Sedgewick's book[START_REF] Flajolet | Analytic Combinatorics[END_REF]. Equivalently, there exist three indices i < j < k such that a i a j a k = 0 and gcd(ji, ki) = 1.

Gz denotes the derivative of G with respect to its second variable.

Gy (resp. Gz) denotes the derivative of G with respect to its first (resp. second) variable.

This research is partially supported by the ANR EGOS, under contract ANR-12-JS02-002-01.

2.1.

Let R ℓ ⊆ R be the set of records of R ending at level ℓ. Since during the execution of Algorithm COLORING_G, every "Uncolor" line follows a "Color" line, a record R ∈ R ℓ can be split into ℓ up-steps (which correspond to the last up-steps between level i and i+1, for each 0 ≤ i ≤ ℓ-1) and ℓ + 1 records {B 1 , B 2 , . . . , B ℓ+1 } ⊆ B (See Figure 3). Hence, the generating function of R ℓ is R ℓ (y) = y ℓ B(y) ℓ+1 . Therefore, Let B j ⊆ B be the set of records of B ending with a descent annotated (j, k) for some k (note that k may take C j distinct possible values by definition). Therefore, a record R ∈ B j ends with a last up-step and a last descent of length s j . The subpath R ′ obtained from R by removing the last up-step and the last descent belongs to R sj -1 . Hence, the generating function of B j is B j (y) = R sj -1 (y) × yC j = y sj C j B(y) sj . Therefore, since a record R ∈ B is either empty (i.e. of size 0) or ends with a descent annotated (j, k), we have:

We are now ready to prove the following theorem.

A The smooth implicit-function schema

In Section 4, we prove Theorem 18 by using a machinery provided by a theorem of Meir and Moon [START_REF] Meir | On an asymptotic method in enumeration[END_REF] (see Theorem 34) on the singular behaviour of generating functions defined by a smooth implicit-function schema.

Definition 33 (Smooth implicit-function schema [15, Definition VII.4, p. 467]) Let A(y) be a function analytic at 0, A(y) = t≥0 a t y t , with a 0 = 0 and a t ≥ 0. The function is said to belong to the smooth implicit-function schema if there exists a bivariate function G(y, z) such that A(y) = G(y, A(y)), where G(y, z) satisfy the following conditions:

(a) G(y, z) = m,n≥0 g m,n y m z n is analytic in a domain |y| < R and |z| < S, for some R, S > 0.

(b) The coefficients of G satisfy g m,n ≥ 0, g 0,0 = 0, g 0,1 = 1, g m,n > 0 for some m ≥ 0 and some n ≥ 2.

(c) There exist two numbers r and s, such that 0 < r < R and 0 < s < S, satisfying the system of equations 4 G(r, s) = s, G z (r, s) = 1, with r < R, s < S which is called the characteristic system.