Xuan Hoang
email: xuan-hoang.la@lirmm.fr

Hoang La

Mickael Montassier
email: mickael.montassier@lirmm.fr

∆ + 2)-coloring of planar graphs with girth at least 10

2-Distance list (∆+2)-coloring of planar graphs with

girth at least 10

Introduction

A k-coloring of the vertices of a graph G = (V, E) is a map φ : V → {1, 2, . . . , k}. A k-coloring φ is a proper coloring, if and only if, for all edge xy ∈ E, φ(x) = φ(y). In other words, no two adjacent vertices share the same color. The chromatic number of G, denoted by χ(G), is the smallest integer k such that G has a proper k-coloring. A generalization of k-coloring is k-list-coloring. A graph G is L-list colorable if for a given list assignment L = {L(v) : v ∈ V (G)} there is a proper coloring φ of G such that for all v ∈ V (G), φ(v) ∈ L(v). If G is L-list colorable for every list assignment L with |L(v)| ≥ k for all v ∈ V (G), then G is said to be k-choosable or k-list-colorable. The list chromatic number of a graph G is the smallest integer k such that G is k-choosable. List coloring can be very different from usual coloring as there exist graphs with a small chromatic number and an arbitrarily large list chromatic number.

In 1969, Kramer and Kramer introduced the notion of 2-distance coloring [START_REF] Kramer | Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz p[END_REF][START_REF] Kramer | Un problème de coloration des sommets d'un graphe[END_REF]. This notion generalizes the "proper" constraint (that does not allow two adjacent vertices to have the same color) in the following way: a 2-distance k-coloring is such that no pair of vertices at distance at most 2 have the same color. The 2-distance chromatic number of G, denoted by χ 2 (G), is the smallest integer k such that G has a 2-distance k-coloring. Similarly to proper k-list-coloring, one can also define 2-distance k-list-coloring We denote χ 2 l (G) the 2-distance list chromatic number of G.

For all v ∈ V , we denote d G (v) the degree of v in G and by ∆(G) = max v∈V d G (v) the maximum degree of a graph G. For brevity, when it is clear from the context, we will use ∆ (resp. d(v)) instead of ∆(G) (resp. d G (v)). One can observe that, for any graph G, ∆ + 1 ≤ χ 2 (G) ≤ ∆ 2 + 1. The lower bound is trivial since, in a 2-distance coloring, every neighbor of a vertex v with degree ∆, and v itself must have a different color. As for the upper bound, a greedy algorithm shows that χ 2 (G) ≤ ∆ 2 + 1. Moreover, that upper bound is tight for some graphs, for example, Moore graphs of type (∆, 2), which are graphs where all vertices have degree ∆, are at distance at most two from each other, and the total number of vertices is ∆ 2 + 1. See Figure 1.

By nature, 2-distance list colorings and the 2-distance list chromatic number of a graph depend a lot on the number of vertices in the neighborhood of every vertex. More precisely, the "sparser" a graph is, the lower its 2-distance chromatic number will be. One way to quantify the sparsity of a graph is through its maximum average degree. The average degree ad of a graph G = (V, E) is defined by ad(G) = 2|E|

|V | . The maximum average degree mad(G) is the maximum, over all subgraphs H of G, of ad(H). Another way to measure the sparsity is through the girth, i.e. the length of a shortest cycle. We denote g(G) the girth of G. Intuitively, the higher the girth of a graph is, the sparser it gets. These two measures can actually be linked directly in the case of planar graphs.

A graph is planar if one can draw its vertices with points on the plane, and edges with curves intersecting only at its endpoints. When G is a planar graph, Wegner conjectured in 1977 that χ 2 (G) becomes linear in ∆(G): Conjecture 1 (Wegner [28]). Let G be a planar graph with maximum degree ∆. Then,

χ 2 (G) ≤    7, if ∆ ≤ 3, ∆ + 5, if 4 ≤ ∆ ≤ 7, 3∆ 2 + 1, if ∆ ≥ 8.
The upper bound for the case where ∆ ≥ 8 is tight (see Figure 2(i)). Recently, the case ∆ ≤ 3 was proved by Thomassen [START_REF] Thomassen | The square of a planar cubic graph is 7-colorable[END_REF], and by Hartke et al. [START_REF] Hartke | The chromatic number of the square of subcubic planar graphs[END_REF] independently. For ∆ ≥ 8, Havet et al. [START_REF] Havet | List colouring squares of planar graphs[END_REF] proved that the bound is

3 2 ∆(1 + o(1)
), where o( 1) is as ∆ → ∞ (this bound holds for 2-distance list-colorings). Conjecture 1 is known to be true for some subfamilies of planar graphs, for example K 4 -minor free graphs [START_REF] Lih | Coloring the square of a K 4 -minor free graph[END_REF]. Wegner's conjecture motivated extensive researches on 2-distance chromatic number of sparse graphs, either of planar graphs with high girth or of graphs with upper bounded maximum average degree which are directly linked due to Proposition 2.

Proposition 2 (Folklore). For every planar graph G, (mad

(G) -2)(g(G) -2) < 4.
As a consequence, any theorem with an upper bound on mad(G) can be translated to a theorem with a lower bound on g(G) under the condition that G is planar. Many results have taken the following form: every graph G of mad(G) ≤ m 0 and ∆(G) ≥ ∆ 0 satisfies χ 2 (G) ≤ ∆(G) + c(m 0 , ∆ 0 ) where c(m 0 , ∆ 0 ) is a small constant depending only on m 0 and ∆ 0 . Due to Proposition 2, as a corollary, we have the same results on planar graphs of girth g ≥ g 0 (m 0 ) where g 0 depends on m 0 . Table 1 shows all known such results, up to our knowledge, on the 2-distance chromatic number of planar graphs with fixed girth, either proven directly for planar graphs with high girth or came as a corollary of a result on graphs with bounded maximum average degree.

g 0 χ 2 (G) ∆ + 1 ∆ + 2 ∆ + 3 ∆ + 4 ∆ + 5 ∆ + 6 ∆ + 7 ∆ + 8 3 ∆ = 3 [27, 16] ∆ ≥ 4 1 2 ∆ ≥ 10 2 ∆ ≥ 12 2 ∆ ≥ 14 2 ∆ ≥ 16 2 4 ∆ ≥ 10 3 ∆ ≥ 12 3 ∆ ≥ 14 3 ∆ ≥ 16 3 ∆ ≥ 18 3 ∆ ≥ 20 3 5 ∆ ≥ 10 7 [1] 6 ∆ = 4 4 ∆ ≥ 339 [14] ∆ ≥ 312 [13] ∆ ≥ 15 [8] 5 ∆ ≥ 12 [7] 6 ∆ = 7, 8 [13] all ∆ [12] 6 ∆ ≥ 17 [3] 9 ∆ ≥ 9 [7] 6 all ∆ [9] 7 ∆ ≥ 16 [18] 6 ∆ ≥ 10 [24] ∆ ≥ 6 [21] 7 ∆ = 4 [10] 7 8 ∆ ≥ 9 [25] 5 ∆ ≥ 6 [24] ∆ ≥ 4 [21] 7 9 ∆ ≥ 7 [23] 9 ∆ = 5 [6] 7 ∆ = 3 [11] 6 10 ∆ ≥ 6 [18] 6 ∆ ≥ 4 8 11 ∆ = 3 [22] ∆ = 4 [10] 7 12 ∆ = 5 [18] 6 ∆ = 3 [5] 6 13 14 ∆ ≥ 4 [2] 9 . . . 21 ∆ = 3 [22]
Table 1: The latest results with a coefficient 1 before ∆ in the upper bound of χ 2 .

For example, the result from line "7" and column "∆ + 1" from Table 1 reads as follows : "every planar graph G of girth at least 7 and of ∆ at least 16 satisfies χ 2 (G) ≤ ∆ + 1". The crossed out cases in the first column correspond to the fact that, for g 0 ≤ 6, there are planar graphs G with χ 2 (G) = ∆ + 2 for arbitrarily large ∆ [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF][START_REF] Dvořák | Coloring squares of planar graphs with girth six[END_REF]. There exists a construction for ∆ = 3, girth 11, and χ 2 ≥ ∆ + 2 detailed in [START_REF] La | 2-distance 4-coloring of planar subcubic graphs with girth at least 21[END_REF]. In Figure 4(i), we show a simple planar graph with girth 4 and χ 2 ≥ ∆ + 3 for all ∆ ≥ 2, which justifies the crossed out cases in the second column. In Figure 4(ii), we show a graph with ∆ = 4, girth 5, and χ 2 ≥ 7. For the first square of the third column, Figure 3 shows graphs with χ 2 ≥ ∆ + 4 for 3 ≤ ∆ ≤ 7 and starting from ∆ ≥ 8, the graph in Figure 2(i) verifies χ 2 ≥ ∆ + 5. Similarly, the rest of the crossed out values of ∆ comes from the constructions in Figure 2 and Figure 3.

We are interested in the case χ 2 (G) ≤ ∆ + 2. More particularly, for a fixed ∆ 0 , we want to find the lowest value g 0 such that planar graphs G with maximum degree ∆ 0 and girth at least

g 0 verify χ 2 (G) ≤ ∆ 0 + 2.
In what follows, we concentrate on the case ∆ 0 = 4. In Figure 4, we provide some simple graphs that give us a lower bound on g 0 depending on ∆ 0 .

For Figure 4(i), u, v and their common neighbors must all be colored differently, say they are colored 1 to ∆ + 1.

The two remaining vertices must be colored with two different colors. As each of them sees every color from 1 to ∆ + 1, they must be colored with ∆ + 2 and ∆ + 3.

For Figure 4(ii), suppose that it is 2-distance colorable with only six colors. Vertices u 1 , u 2 , u 3 , u 4 , and u 5 form a cycle of length 5 so they must all be colored differently, say u i is colored i for 1 ≤ i ≤ 5. Vertex u 6 sees every color from 1 to 5 so it must be colored 6. Vertex u 2 sees every color except 2 so it must be colored 2. Finally, u 7 sees every color from 1 to 6, which is a contradiction. Now, for the upper bound on g 0 , we are going to prove that g 0 ≤ 10. In other words,

Theorem 3. If G is a planar graph with g(G) ≥ 10 and ∆(G) ≥ 4, then χ 2 (G) ≤ ∆(G) + 2.
As the following results are already known: 5 Corollaries of more general colorings of planar graphs. 6 Corollaries of 2-distance list-colorings of planar graphs. 7 Corollaries of 2-distance list-colorings of graphs with a bounded maximum average degree. 8 Corollary of our result. 9 Corollaries of 2-distance colorings of graphs with a bounded maximum average degree. Theorem 4 (Bu et al. [START_REF] Bu | The list 2-distance coloring of a graph with ∆(G) = 5[END_REF]). If G is a planar graph with g(G) ≥ 9 and ∆(G) = 5, then χ 2 (G) ≤ ∆(G) + 2.

1 Figure 3 2 Figure 2(i) 3 Figure 2(ii) 4 Figure 4(ii)
Theorem 5 (La and Montassier [24]). If G is a planar graph with g(G) ≥ 8 and

∆(G) ≥ 6, then χ 2 (G) ≤ ∆(G) + 2.
we only need to prove that:

Theorem 6. If G is a planar graph with g(G) ≥ 10 and ∆(G) = 4, then χ 2 (G) ≤ 6.
We will be proving a slightly stronger version which states:

Theorem 7. If G is a graph with mad(G) < 5 2 , g(G) ≥ 10 and ∆(G) = 4, then χ 2 l (G) ≤ 6.
The latter also improves upon a result from [START_REF] Cranston | Choosability of the square of a planar graph with maximum degree four[END_REF].

Theorem 8 (Cranston et al. [START_REF] Cranston | Choosability of the square of a planar graph with maximum degree four[END_REF]). If G is a planar graph with g(G) ≥ 11 and ∆(G) = 4, then χ 2 l (G) ≤ 6. In Section 2, we present the proof of Theorem 7 using the well-known discharging method.

Proof of Theorem 7

Notations and drawing conventions.

For v ∈ V (G), the 2-distance neighborhood of v, denoted N * G (v)
, is the set of 2-distance neighbors of v, which are vertices at distance at most two from v, not including v. We also denote

d * G (v) = |N * G (v)|.
We will drop the subscript and the argument when it is clear from the context. Also for conciseness, from now on, when we say "to color" a vertex, it means to color such vertex differently from all of its colored neighbors at distance at most two. Similarly, any considered coloring will be a 2-distance list-coloring. We will also say that a vertex u "sees" another vertex v if u and v are at distance at most 2 from each other. Some more notations:

• A d-vertex (d + -vertex, d --vertex) is a vertex of degree d (at least d, at most d). A (d ↔ e)-vertex is a
vertex of degree between d and e included.

• A k-path (k + -path, k --path) is a path of length k + 1 (at least k + 1, at most k + 1) where the k internal vertices are 2-vertices and the endvertices are 3 + -vertices.

• A (k 1 , k 2 , . . . , k d )-vertex is a d-vertex incident to d different paths, where the i th path is a k i -path for all 1 ≤ i ≤ d.

As a drawing convention for the rest of the figures, black vertices will have a fixed degree, which is represented, and white vertices may have a higher degree than what is drawn.

Let G be a counterexample to Theorem 7 with the fewest number of vertices. The purpose of the proof is to prove that G cannot exist. In the following sections, we will study the structural properties of G (Section 2.2), then, we will apply a discharging procedure (Section 2.3).

Useful observations

Before studying the structural properties of G, we will introduce some useful observations and lemmas that will be the core of the reducibility proofs of our configurations.

For a vertex u, let L(u) denote the set of available colors for u. For convenience, the lower bound on |L(u)| will be depicted on the figures below the corresponding vertex u.

Lemma 9. Every graph with list assignment L depicted in Figure 5 is L-list-colorable.

Proof. In the following proofs, whenever the size of a list |L(u)| ≥ i, we assume that |L(u)| = i by removing the extra colors from the list.

(i) If L(u 1 ) = L(u 2 ), then we color u 3 with a color in L(u 3 ) \ L(u 2 ), followed by u 4 , u 2 , and u 1 in this order. If L(u 1 ) = L(u 2 ), then we color u 2 with a color in L(u 2 ) \ L(u 1 ), followed by u 4 , u 3 , and u 1 in this order.

(ii) First, we claim the following:

-L(u 5 )∩L(u 1 ) = ∅ and L(u 5 )∩L(u 2 ) = ∅. Suppose by contradiction that there exists x ∈ L(u 5 )∩L(u 1 ), we color u 1 and u 5 with x, then u 2 , u 3 , u 3 , u 3 , and u 4 in this order. The same argument holds for L(u 5 ) ∩ L(u 2 ).

-L(u 5 ) ∩ L(u 3 ) = ∅. Suppose by contradiction that there exists x ∈ L(u 5 ) ∩ L(u 3 ), we color u 3 and u 5 with x. Observe that L(u 5 ) ∩ L(u 1 ) = ∅ and L(u 5 ) ∩ L(u 2 ) = ∅. So, we color u 3 , u 3 , u 2 , u 1 , and u 4 in this order.

-L(u 5 ) ∩ L(u 3 ) = ∅. Otherwise, we color u 3 with x ∈ L(u 5 ) ∩ L(u 3 ). Observe that L(u 5 ) ∩ L(u 1 ) = ∅, L(u 5 ) ∩ L(u 2 ) = ∅, and L(u 5 ) ∩ L(u 3 ) = ∅. So, we color u 5 , u 3 , u 2 , u 1 , u 4 , and u 3 in this order.

Since L(u 5 ) ∩ L(u 3 ) = ∅, we color u 2 , u 1 , u 3 , u 3 , u 3 , u 4 , and u 5 in this order.

(iii) First, we claim that L(v 3 ) ⊂ L(v 3 ). Otherwise, we color v 3 with x ∈ L(v 3 ) \ L(v 3 ). Then, we color everything else except v 3 thanks to Figure 5ii. We finish by coloring v 3 .

Now, we color

u 3 with x ∈ L(u 3 ) \ L(v 3 ). Since L(v 3 ) ⊂ L(v 3 ), x / ∈ L(v 3
). Thus, we color u 2 , u 1 , u 3 , u 5 , u 4 , u 3 , v 3 , and v 3 in this order.

(iv) First, we claim that L(v 3 ) ⊂ L(v 3 ) and L(v 5 ) ⊂ L(v 5 ). Suppose by contradiction that there exists

x ∈ L(v 5 ) \ L(v 5 ). We color v 5 with x. Then, we color everything else except v 5 thanks to Figure 5iii. We finish by coloring v 5 . Symmetrically, the same holds for L(v 3 ) ⊂ L(v 3 ). Now, we color u 3 with x ∈ L(u 3 ) \ L(v 3 ). Since L(v 3 ) ⊂ L(v 3 ), x / ∈ L(v 3 ). Similarly, we color u 5 with y ∈ L(u 5 ) \ L(v 5 ). We finish by coloring u 3 , u 2 , u 1 , u 3 , v 3 , v 3 , u 4 , v 5 , and v 5 in this order.

(v) First, we claim the following:

-L(u 2 )∩L(u 5 ) = ∅ and L(u 2 )∩L(u 3 ) = ∅. Suppose by contradiction that there exists x ∈ L(u 2 )∩L(u 5 ).

We color u 2 and u 5 with x, then u 1 , u 3 , u 3 , u 3 , and v 4 in this order. Symmetrically, the same holds for L(u 2 ) ∩ L(u 3 ).

-L(u 3 ) ⊂ (L(u 5 ) ∪ L(u 3 )). Suppose by contradiction that there exists x ∈ L(u 3 ) \ (L(u 5 ) ∪ L(u 3 )).

We color u 3 with x, then u 1 , u 2 , u 3 , u 3 , u 4 , then u 5 in this order.

-L(u 3 )∩L(u 5 ) = ∅ and L(u 4 )∩L(u 3 ) = ∅. Suppose by contradiction that there exists x ∈ L(u 3 )∩L(u 5 ). We color u 3 and u 5 with x. Observe that x / ∈ L(u 2 ) since L(u 2 ) ∩ L(u 5 ) = ∅. Thus, we color u 3 , u 3 , u 1 , u 2 and u 4 in this order. Symmetrically, the same holds for L(u 4 ) ∩ L(u 3 ).

Since L(u 3 ) ⊂ (L(u 5 )∪L(u 3 )), |L(u 3 )| = 3, and |L(u 5 )| = |L(u 3 )| = 2, there must exist x ∈ L(u 5 )∩L(u 3 ). In addition, x / ∈ L(u 3 ) as L(u 3 ) ∩ L(u 5 ) = ∅. Thus, we color u 3 with x, then u 1 , u 2 , u 5 , u 4 , u 3 , and u 3 in this order.

(vi) First, we claim that L(v 3 ) ⊂ L(v 3 ). Otherwise, we color v 3 with x ∈ L(v 3 ) \ L(v 3 ). Then, we color everything else except v 3 thanks to Figure 5v. We finish by coloring v 3 .

Now, we color

u 3 with x ∈ L(u 3 ) \ L(v 3 ). Since L(v 3 ) ⊂ L(v 3 ), x / ∈ L(v 3
). Thus, we color u 1 , u 3 , u 2 , u 5 , u 4 , u 3 , v 3 , and v 3 in this order.

(vii) First, we claim that L(v 3 ) ⊂ L(v 3 ) and L(v 5 ) ⊂ L(v 5 ). Suppose by contradiction that there exists

x ∈ L(v 5 ) \ L(v 5 ). We color v 5 with x. Then, we color everything else except v 5 thanks to Figure 5vi. We finish by coloring v 5 . Symmetrically, the same holds for L(v 3 ) ⊂ L(v 3 ).

u 1 2 u 2 2 u 3 3 u 4 2 (i) u 1 3 u 3 3 u 4 5 u 5 2 u 3 5 u 3 2 u 2 2 (ii) u 1 3 u 3 4 u 4 5 u 5 2 u 2 2 u 3 6 u 3 4 v 3 3 v 3 2 (iii) u 1 3 u 3 4 u 4 6 u 5 4 u 2 2 u 3 6 u 3 4 v 3 3 v 3 2 v 5 3 v 5 2 (iv) u 1 2 u 2 3 u 3 3 u 4 4 u 5 2 u 3 4 u 3 2 (v)
∈ L(u 3 ) \ L(v 3 ). Since L(v 3 ) ⊂ L(v 3 ), x / ∈ L(v 3
). Similarly, we color u 5 with y ∈ L(u 5 ) \ L(v 5 ). We finish by coloring u 3 , u 1 , u 2 , u 3 , v 3 , v 3 , u 4 , v 5 , and v 5 in this order.

(viii) First, we claim that L(u 0 ) = L(u 1 ). Otherwise, we color u 0 with x ∈ L(u 0 ) \ L(u 1 ). Then, we color the rest thanks to Figure 5v.

Since L(u 0 ) = L(u 1 ), we can restrict L(u 2 ) to L (u 2 ) = L(u 2 ) \ L(u 1 ) and observe that, if we can color everything (where u 2 has list L (u 2 )) except u 0 and u 1 , then we can always finish by coloring u 1 and u 0 in this order.

Let us show that everything except u 0 and u 1 can be colored first with the new list L (u 2 ) for u 2 . We claim the following:

-L(u 5 ) ∩ L (u 2 ) = ∅. Otherwise, we color u 2 and u 5 with x ∈ L(u 5 ) ∩ L (u 2 ). Then, we color u 3 , u 3 , u 3 , and u 4 in this order.

-L(u 5 ) ∩ L(u 3 ) = ∅. Otherwise, we color u 3 and u 5 with x ∈ L(u 5 ) ∩ L(u 3 ). Observe that L(u 5 ) ∩ L (u 2 ) = ∅ so x / ∈ L (u 2 ). So, we color u 3 , u 3 , u 2 , and u 4 in this order.

-L(u 5 ) ∩ L(u 3 ) = ∅. Otherwise, we color

u 3 with x ∈ L(u 5 ) ∩ L(u 3 ). Observe that L(u 5 ) ∩ L (u 2 ) = ∅ and L(u 5 ) ∩ L(u 3 ) = ∅ so x / ∈ L (u 2 ) ∪ L(u 3
). So, we color u 5 , u 3 , u 2 , u 4 , and u 3 in this order.

Since L(u 5 ) ∩ L(u 3 ) = ∅, we color u 2 , u 3 , u 3 , u 3 , u 4 , and u 5 in this order.

(ix) First, we claim that L(v 3 ) ⊂ L(v 3 ). Otherwise, we color v 3 with x ∈ L(v 3 ) \ L(v 3 ). Then, we color eveything else except v 3 thanks to Figure 5viii. We finish by coloring v 3 . Now, we color

u 3 with x ∈ L(u 3 ) \ L(v 3 ). Since L(v 3 ) ⊂ L(v 3 ), x / ∈ L(v 3
). Thus, we color u 0 , u 1 , u 3 , u 2 , u 5 , u 4 , u 3 , v 3 , and v 3 in this order.

(x) First, we claim that L(v 3 ) ⊂ L(v 3 ) and L(v 5 ) ⊂ L(v 5 ). Suppose by contradiction that there exists

x ∈ L(v 5 ) \ L(v 5 ). We color v 5 with x. Then, we color everything else except v 5 thanks to Figure 5ix. We finish by coloring v 5 . Symmetrically, the same holds for

L(v 3 ) ⊂ L(v 3 ). Now, we color u 3 with x ∈ L(u 3 ) \ L(v 3 ). Since L(v 3 ) ⊂ L(v 3 ), x / ∈ L(v 3
). Similarly, we color u 5 with y ∈ L(u 5 ) \ (L(v 5 ) ∪ L(v 5 )). We finish by coloring u 3 , u 1 , u 0 , u 2 , u 3 , v 3 , v 3 , u 4 , v 5 , and v 5 in this order. Proof. By Lemma 10, the minimum degree is at least 1 or G would be a single isolated vertex contradicting ∆(G) = 4. If G contains a degree 1 vertex v, then we can simply remove v and 2-distance color the resulting graph, which is possible by minimality of G. Then, we add v back and extend the coloring (at most 4 constraints and 6 colors). Proof. Suppose by contradiction that G does contain three consecutives 2-vertices uvw (see Figure 6i). It suffices to color G -{u, v, w} by minimality of G, then we can extend the coloring to the remaining vertices by coloring u, w, then v in this order. This is possible since u, v, and w have respectively at least 2, 4, and 2 colors left available.

Structural properties of G

• If u is a (1 + , 1 + , 1 + , 0)-vertex with a 3-neighbor, then let uu i v i be the 1 + -paths incident to u for 1 ≤ i ≤ 3. We know that u always give 1 to its 3-neighbor.

If at most one of the v i 's is a light vertex, then at worst

µ * (u) ≥ 6 -1 -2 -2 • 4 3 = 1 3 .
If at least two of the v i 's are light vertices, say v 1 and v 2 , then v 3 must be a non-special (1, 1, 0)-endvertex, a (1, 0, 0)-endvertex or a 4-endvertex due to Lemma 20. As a result, u gives only 1 to uu 3 v 3 . Thus, at worst we get µ * (u) ≥ 6 -1 -2 • 2 -1 = 0.

• If u is a (0 + , 0 + , 0, 0)-vertex, then at worst we have

µ * (u) ≥ 6 -2 • 2 -2 • 1 = 0.
To conclude, we started with a charge assignment with a negative total sum, but after the discharging procedure, which preserved that sum, we end up with a non-negative one, which is a contradiction. In other words, there exists no counter-example to Theorem 7.

Remarks

Graphs of with mad < 5 2 contains all planar graphs with girth at least 10. The condition on the girth in Theorem 7 only serves to simplify the proof of the reducibility of certain configurations as it guarantees that some vertices must be distinct. Here, we chose girth 10 as it would coincide with the girth of the subclass of planar graphs, but girth 9 suffices to guarantee the desired property. One can also strengthen Theorem 7 by removing this condition and study the cases where some vertices in our configurations coincide.

  The Moore graph of type (2,2): the odd cycle C5.

  The Moore graph of type (3,2): the Petersen graph. (iii) The Moore graph of type (7,2): the Hoffman-Singleton graph.

Figure 1 :

 1 Figure 1: Examples of Moore graphs for which χ 2 = ∆ 2 + 1.

Figure 2 :

 2 Figure 2: Graphs with χ 2 ≈ 3 2 ∆ [28].

(i) ∆ = 3 and χ 2

 2 ≥ 7. (ii) ∆ = 4 and χ 2 ≥ 9.(iii) ∆ = 5 and χ 2 ≥ 10.(iv) 6 ≤ ∆ ≤ 7 and χ 2 ≥ ∆ + 5.

Figure 3 :

 3 Figure 3: Constructions by Wegner in [28].

∆

  -1 vertices (i) A graph with girth 4 and χ 2 ≥ ∆ + 3.

2 (

 2 ii) A graph with ∆ = 4, girth 5, and χ 2 ≥ 7.

Figure 4 :

 4 Figure 4: Graphs with χ 2 ≥ ∆ + 3.

Figure 5 :

 5 Figure 5: List-colorable graphs.

Lemma 10 .Lemma 11 .

 1011 Graph G is connected.Proof. Otherwise a component of G would be a smaller counterexample. The minimum degree of G is at least 2.

1 x

 1 (ii) A 2-path incident to a 3-vertex.

Figure 6 :

 6 Figure 6: Path cases.

Acknowledgements

This work was partially supported by the grant HOSIGRA funded by the French National Research Agency (ANR, Agence Nationale de la Recherche) under the contract number ANR-17-CE40-0022.

Lemma 13. An endvertex of a 2-path must be a 4-vertex.

Proof. Suppose by contradiction that there exists a 2-path uvwx where d(u) = 3 (see Figure 6ii). We color G -{v, w} by minimality of G. Then, we color w and v in this order since they have respectively at least 1 and 2 colors left available.

Let us define some nomenclatures. Definition 14. Let u be a (1, 1, 1)-vertex and let v, w, and x be the other endvertices of the 1-paths incident to u. We call u

• a small (1, 1, 1)-vertex, if v, w, and x are all 3-vertices.

• a medium (1, 1, 1)-vertex, if exactly one of v, w, and x is a 4-vertex.

• a large (1, 1, 1)-vertex, if exactly two of v, w, and x are 4-vertices.

• a huge (1, 1, 1)-vertex, if v, w, and x are all 4-vertices.

Definition 15. Let u be a (1, 1, 0)-vertex with a 3-neighbor and let u share a common 2-neighbor with a small (1, 1, 1)-vertex. We call u a special (1, 1, 0)-vertex. Definition 16. We call u a light vertex if u is a 2-vertex, a medium (1, 1, 1)-vertex, or a large (1, 1, 1)-vertex. Proof. Let uu 1 v be a 1-path where both u and v are (1, 1, 1)-vertices. Let u 2 and u 3 be u's other 2-neighbors and v 1 and v 2 be v's other 2-neighbors. Let w be the other endvertex of wu 2 u. Since g(G) ≥ 10, all named vertices are distinct. See Figure 9i.

Suppose by contradiction that d(w) = 3, in other words, that u is not a large (1, 1, 1)-vertex. We color G -{u, u 1 , u 2 , u 3 } by minimality of G and uncolor v. Then, we color u 3 and finish with u 2 , u, u 1 , and v thanks to Figure 5i.

Lemma 18. A special (1, 1, 0)-vertex must share a 2-neighbor with a 4-vertex.

Proof. Let u 2 u 3 u 4 be a 1-path where u 2 is a special (1, 1, 0)-vertex and u 4 is a small (1, 1, 1)-vertex. Let u 1 = u 3 be u 2 's other 2-neighbor. See Figure 9ii. Suppose by contradiction that u 1 is adjacent to another 3-vertex. Since g(G) ≥ 10, all vertices that see u 3 are distinct. We color G -{u 1 , u 2 , u 3 } by minimality of G and we uncolor u 4 . We extend the coloring to u 1 , u 2 , u 3 , and u 4 thanks to Figure 5i. Proof. Suppose by contradiction that v 1 and v 2 are light vertices but d(v 3 ) ≤ 3. (see Figure 10i). The proof will proceed as follows. For each combination of light vertices v 1 and v 2 , we will define H a subgraph of G. We color G -H by minimality of G. Then, let L(x) be the list of remaining colors for every x ∈ V (H). We will use Figure 5 to show that H is always colorable, thus obtaining a valid coloring G, which is a contradiction. Observe that g(G) ≥ 10 so g(H) ≥ 10, which means that, in the following subgraphs, every considered vertex will be distinct and their neighborhood at distance at most 2 will be represented exactly by the subgraphs in Figure 5.

By symmetry, the same holds for d(v 4 ).

Lemma 20. Let u be a 4-vertex with a 3-neighbor and let u be incident to three

Proof. Suppose by contradiction that v 1 and v 2 are light vertices but v 3 is a 2-vertex, a special (1, 1, 0)-vertex, or a (1, 1, 1)-vertex (see Figure 10ii).

We will proceed like the proof of Lemma 19 by defining a certain subgraph H, coloring G -H and extending it to H by using Figure 5.

Let v 3 be a special (1, 1, 0)-vertex or a light vertex. When v 3 is a 3-vertex, note that v 3 always has a 2-neighbor v that is adjacent to another 3-vertex different from v 3 . We define

) is colorable thanks to Figure 5viii when N G (v 3 ) = {v} or Figure 5v otherwise.

• If v 1 is a 2-vertex and v 2 is a medium or large (1, 1, 1)-vertex, then

) is colorable thanks to Figure 5ix when N G (v 3 ) = {v} or Figure 5vi otherwise.

• If v 1 and v 2 are medium or large (1, 1, 1)-vertices, then

) is colorable thanks to Figure 5x when N G (v 3 ) = {v} or Figure 5vii otherwise.

Let v 3 be a huge (1, 1, 1)-vertex. In the following cases, we actually remove everything in H except v 3 , color G -(H \ {v 3 }), then uncolor v 3 , and we extend the coloring to H.

is colorable thanks to Figure 5vi.

• If v 1 and v 2 are medium or large (1, 1, 1)-vertices, then

) is colorable thanks to Figure 5vii.

Discharging rules

Since mad(G) < 5 2 , we must have

We assign to each vertex u the charge µ(u) = 4d(u) -10. To prove the non-existence of G, we will redistribute the charges preserving their sum and obtaining a non-negative total charge, which will contradict Equation (1).

We then apply the following discharging rules: R0 Every 3 + -vertex gives 1 to each 2-vertex on its incident 1 + -paths.

R1 Every 4-vertex gives 1 to each of its 3-neighbors.

R2

Let vtu be a 1-path.

(i) If v is a (1, 1 -, 0)-vertex and u is a small (1, 1, 1)-vertex, then v gives 1 3 to u. (ii) If v is a 4-vertex and u is a medium (1, 1, 1)-vertex, then v gives 1 to u.

(iii) If v is a 4-vertex and u is a large (1, 1, 1)-vertex, then v gives 1 2 to u. (iv) If v is a 4-vertex and u is a huge (1, 1, 1)-vertex, then v gives 1 3 to u. (v) If v is a 4-vertex and u is a special (1, 1, 0)-vertex, then v gives 1 3 to u.

(iii) Large (1, 1, 1)-vertex case.

(iv) Huge (1, 1, 1)-vertex case.

Verifying that charges on each vertex are non-negative

Let µ * be the assigned charges after the discharging procedure. In what follows, we will prove that:

Let u be a vertex in V (G). Case 1: If d(u) = 2, then u receives charge 1 from each endvertex of the path it lies on by R0. Thus, we get:

Moreover, u cannot be incident to any 2 + -paths due to Lemmas 12 and 13. Now, we distinguish the following cases:

• If u is a (1, 1, 1)-vertex, then u only gives charge to its 2-neighbors, more precisely 1 to each of its 2-neighbors by R0. Let v, w, and x be the other endvertices of the 1-paths incident to u.

If u is a small (1, 1, 1)-vertex, then observe that v, w, and x are all (1, 1 -, 0)-vertices as they cannot be (1, 1, 1)-vertices due to Lemma 17. As a result, u receives 1 3 from each of v, w, and x by R2(i). Hence,

If u is a medium (1, 1, 1)-vertex, then u receives 1 from one of v, w, and x by R2(ii). Hence,

If u is a large (1, 1, 1)-vertex, then u receives 1 2 twice from v, w, and x by R2(iii). Hence,

If u is a huge (1, 1, 1)-vertex, then u receives 1 3 from each of v, w, and x by R2(iv). Hence,

• If u is a (1, 1, 0)-vertex, then u gives 1 to each of its 2-neighbors by R0. Let t be its 3 + -neighbor and let v and w be the other endvertices of the 1-paths incident to u. First, observe that if neither v nor w is a small (1, 1, 1)-vertex, then we would have

So, say v is a small (1, 1, 1)-vertex, in which case, u gives 1 3 to v by R2(i). If d(t) = 4, then u receives 1 from t by R1. Moreover, at worst, u also gives 1 3 to w by R2(i). To sum up,

If d(t) = 3, then w must be a 4-vertex by Lemma 18. In other words, u is a special (1, 1, 0)-vertex. Thus, u receives 1 3 from w by R3. To sum up,

• If u is a (1, 0, 0)-vertex, then at worst, u gives 1 to its 2-neighbor by R0 and 1 3 to the other endvertex of its incident 1-path by R2(i). Thus,

• If u is a (0, 0, 0)-vertex, then none of the discharging rules apply. Thus,

Case 3: If d(u) = 4, then recall that µ(u) = 4 • 4 -10 = 6. Observe that u gives away at most 2 per incident 0 + -path. Indeed, there are no 3 + -paths by Lemma 12. More precisely, u gives:

2 to a 2-path by R0.

2 to a 1-path with a medium (1, 1, 1)-endvertex by R0 and R2(ii). 1 to a 1-path with a non-special (1, 1, 0)-endvertex, a (1, 0, 0)-endvertex or a 4-endvertex by R0.

1 to a 3-neighbor by R1.

Observe that u only gives more than 4 3 to an incident path when the neighbor at distance 2 on that path is a light vertex (Definition 16). Now, we distinguish the following cases:

• If u is a (1 + , 1 + , 1 + , 1 + )-vertex, then let uu i v i be the 1 + -paths incident to u for 1 ≤ i ≤ 4.

If at most one of the v i 's is a light vertex, then at worst • If u is a (1 + , 1 + , 1 + , 0)-vertex with a 4-neighbor, then u does not give anything to its 4-neighbor. Thus, at worst we have µ * (u) ≥ 6 -3 • 2 = 0.