Manu Basavaraju

L Sunil Chandran

NATHANN COHEN § , FR ÉD ÉRIC HAVET § Tobias M Üller
email: tobias@cwi.nl

L S Chandran

N Cohen

F Havet
email: fhavet@sophia.inria.fr.

T Müller It

ACYCLIC EDGE-COLOURING OF PLANAR GRAPHS *

Keywords: spanning galaxy, even strong subdigraph, directed star arboricity

A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an acyclic edge-colouring. The acyclic chromatic index of a graph G, denoted χ a (G), is the minimum k such that G admits an acyclic edge-colouring with k colours. We conjecture that if G is planar and ∆(G) is large enough then χ a (G) = ∆(G). We settle this conjecture for planar graphs with girth at least 5. We also show that χ a (G) ≤ ∆(G) + 12 for all planar G, which improves a previous result by Fiedorowicz et al. [12].

Introduction.

A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an acyclic edge-colouring. The acyclic chromatic index of a graph G, denoted χ a (G), is the minimum k such that G admits an acyclic edge-colouring with k colours. Fiamčik [START_REF] Fiamčik | The acyclic chromatic class of a graph (in russian)[END_REF] and later Alon, Sudakov and Zaks [START_REF] Alon | Acyclic edge-colorings of graphs[END_REF] conjecture that ∆(G) + 2 colours are enough.

Conjecture 1.1 (Fiamčik [9]-Alon, Sudakov and Zaks [START_REF] Alon | Acyclic edge-colorings of graphs[END_REF]). For every graph G, χ a (G) ≤ ∆(G)+2. This conjecture would be tight as there are cases where more than ∆+1 colours are needed. Consider for example a graph G on 2n vertices with at least 2n 2 -2n+2 edges. The union of two perfect matchings is a cycle factor and thus contains a cycle. Thus, in an acyclic edge-colouring, at most one colour class contains n edges. Hence there are at least 1 + 2n 2 -3n+2 n-1 = 2n + 1 colours. So χ a (G) ≥ ∆(G) + 2. Clearly, every graph with maximum degree at most 2 has acyclic chromatic index at most 3. If ∆(G) ≤ 3 then its line-graph L(G) has maximum degree at most 4. Thus by Burnstein's results [START_REF] Burnstein | Every 4-valent graph has an acyclic 5-coloring (in Russian)[END_REF] χ a (L(G)) ≤ 5 and so χ a (G) ≤ 5. So Conjecture 1.1 holds for ∆(G) ≤ 3. In 1980, Fiamčik [START_REF] Fiamčik | Acyclic chromatic index of a graph with maximum valency three[END_REF] conjectured that K 4 is the only cubic graph requiring five colours in an acyclic edge-colouring (and actually gave an uncorrect proof of it). More generally, Alon, Sudakov and Zaks [START_REF] Alon | Acyclic edge-colorings of graphs[END_REF] conjectured that if G is a ∆-regular graph then χ a (G) = ∆ + 1 unless G = K 2n .

However as noted by Fiamčik [START_REF] Fiamčik | Acyclic chromatic index of subdivided graph[END_REF], these two conjectures are false as χ a (K 3,3 ) = 5. In addition, Basavaraju, Chandran and Kummini [START_REF] Basavaraju | d-regular graphs with acyclic chromatic index at least d + 2[END_REF] showed that all d-regular graphs with 2n vertices and d > n, require at least d + 2 colours to be acyclically edge-coloured and for every odd n, χ a (K n,n ) = n + 2. They also showed that for every d, n such that d ≥ 5, n ≥ 2d + 3 and dn even, there exist d-regular graphs which require at least d + 2-colours to be acyclically edge-coloured.

Alon, Sudakov and Zaks [START_REF] Alon | Acyclic edge-colorings of graphs[END_REF] showed that Conjecture 1.1 is true for almost all regular graphs. This was later improved by Nešetřil and Wormald [START_REF] Nešetřil | The acyclic edge chromatic number of a random d-regular graph is d + 1[END_REF] who proved that the acyclic edge-chromatic number of a random ∆-regular graph is asymptotically almost surely equal to ∆ + 1. Alon, McDiarmid and Reed [START_REF] Alon | Acyclic colouring of graphs[END_REF] showed an upper bound of 64∆(G) for χ a (G) which was later improved to 16∆(G) by Molloy and Reed [START_REF] Molloy | Further algorithmic aspects of Lovasz Local Lemma[END_REF]. For graphs with large girth, better upper bounds are known. Muthu et al [START_REF] Muthu | Improved bounds on acyclic edge colouring[END_REF] showed that, if G has girth at least 9, then χ a (G) ≤ 6∆(G), and, if it has girth at least 220, then χ a (G) ≤ 4.52∆(G). Finally, Alon, Sudakov and Saks also showed that Conjecture 1.1 is true for graphs with girth at least C∆ log(∆) for some fixed constant C. [START_REF] Muthu | Acyclic edge colouring of outerplanar graphs[END_REF] proved that χ a (G) ≤ ∆(G) + 1 for outerplanar graphs. Fiedorowicz et al. [START_REF] Fiedorowicz | About acyclic edge colouring of planar graphs[END_REF] proved that χ a (G) ≤ 2∆(G) + 29 if G is planar and χ a (G) ≤ ∆(G) + 6 if G is planar and triangle-free. This bound has been improved for planar graphs with larger girth. Recall that the girth of a graph is the minimum length of a cycle it contains or +∞ if it has no cycles. Hou et al. [START_REF] Hou | Acyclic edge colorings of planar graphs and series-parallel graphs[END_REF] showed that if G is a planar graph G then χ a (G) ≤ ∆(G) + 2 if G has girth at least 5, χ a (G) ≤ ∆(G) + 1 if G has girth at least 7 and χ a (G) ≤ ∆(G) if G has girth at least 16 and ∆(G) ≥ 3.

Muthu et al

Sanders and Zhao [START_REF] Sanders | Planar graphs of maximum degree seven are class I[END_REF] showed that planar graphs with maximum degree ∆ ≥ 7 have chromatic index ∆. A conjecture of Vizing [START_REF] Vizing | Critical graphs with given chromatic index[END_REF] asserts that planar graphs of maximum degree 6 are also 6-edge-colourable. This would be best possible as for any ∆ ∈ {2, 3, 4, 5}, there are some planar graphs with maximum degree ∆ with chromatic index ∆ + 1 [START_REF] Vizing | Critical graphs with given chromatic index[END_REF].

We propose a conjecture analogous to the above one of Vizing. Conjecture 1.2. There exists ∆ 0 such that every planar graph with maximum degree ∆ ≥ ∆ 0 has an acyclic edge-colouring with ∆ colours.

In this paper, we give some evidences to this conjecture. Firstly, in Section 2, we show that every planar graph G has an acyclic edge-colouring with ∆(G)+12 colours thus improving the 2∆(G)+29 bound of Fiedorowicz et al. [START_REF] Fiedorowicz | About acyclic edge colouring of planar graphs[END_REF]. In Section 3, we show that Conjecture 1.2 holds for planar graphs of girth at least 5 (with ∆ 0 = 19) thus improving the results of Hou et al. [START_REF] Hou | Acyclic edge colorings of planar graphs and series-parallel graphs[END_REF] and Borowiecki and Fiedorowicz [START_REF] Borowiecki | Acyclic edge colouring of planar graphs without short cycles Discrete Math[END_REF]. More generally, we settle Conjecture 1.2 for graphs with maximum average degree less than 4 -for any > 0. The maximum average degree of

G is M ad(G) = max{ 2|E(H)| |V (H)| | H is a subgraph of G}.
It is well known that a planar graph of girth g has maximum average degree less than 2 + 4 g-2 . Conjecture 1.2 holds for outerplanar graphs with ∆ 0 = 5 as shown by Hou et al. [START_REF] Hou | Acyclic edge chromatic number of outerplanar graphs[END_REF]. Note that sup{M ad(G) | G is outerplanar} = 4.

Our proofs are constructive and yield efficient polynomial time algorithms. We present the proofs in a non-algorithmic way. But it is easy to extract the underlying algorithms from them.

2. Planar graphs. In this section we will prove the following result. Theorem 2.1. χ a (G) ≤ ∆(G) + 12 for all planar graphs G. The proof of Theorem 2.1 relies on the following theorem of van den Heuvel and McGuiness [START_REF] Van Den Heuvel | Coloring the square of a planar graph[END_REF] which establishes a set of unavoidable configurations in planar graphs.

Lemma 2.2 (van den Heuvel and McGuiness [START_REF] Van Den Heuvel | Coloring the square of a planar graph[END_REF]). Let G be a planar graph with minimum degree at least two. Then there exists a vertex v in G with exactly

d(v) = k neighbours v 1 , v 2 , . . . , v k with d(v 1 ) ≤ d(v 2 ) ≤ . . . ≤ d(v k ) such that at least one of the following is true: (A1) k = 2, (A2) k = 3 and d(v 1 ) ≤ 11, (A3) k = 4 and d(v 1 ) ≤ 7, d(v 2 ) ≤ 11, (A4) k = 5 and d(v 1 ) ≤ 6, d(v 2 ) ≤ 7, d(v 3 ) ≤ 11.
Sketch of the proof of Theorem 2.1:. Let G be a minimum counter-example with respect to the number of vertices and edges for the statement in Theorem 2.1. Trivially G has minimum degree at least 2. Indeed, it has no vertex v of degree 0 because any acyclic edge-colouring of G -v is an acyclic edge-colouring of G, and it has no vertex v with a unique neighbour u, since any acyclic edge-colouring of G -v on at least ∆(G) colours may be extended to an acyclic edge-colouring of G by assigning to uv a colour not already assigned to an edge incident to u. From Lemma 2.2, we know that there exists a vertex v in G such that it belongs to one of the configurations A1-A4. If there is a configuration A 2 , A 3 and A 4 in G, we show in Subsection 2.2 how to derive an acyclic edge-colouring with ∆(G) + 12 colours of G from one of G \ vv 1 . Hence, we assume that there is no such configurations. In such case, we select an appropriate edge uu and show again how to derive an acyclic edge-colouring of G with ∆(G) + 12 colours from one of G \ uu . This gives a final contradiction. See Subsection 2.3.

In order to show how to extend an acyclic edge-colouring of G \ e for some edge e into an acyclic edge-colouring of G,we first establish some preliminaries.

Preliminaries.

Partial edge-colouring:. Let H be a subgraph of G. Then an edge-colouring c of H is also a partial edge-colouring of G. Note that H can be G itself. Thus an edge-colouring c of G itself can be considered a partial edge-colouring. A partial edge-colouring c of G is said to be a proper partial edge-colouring if c is proper. A proper partial edge-colouring c is called acyclic if there are no bichromatic cycles in the graph. Note that with respect to a partial edge-colouring c, c(e) may not be defined for an edge e. So, whenever we use c(e), we are considering an edge e for which c(e) is defined, though we may not always explicitly mention it.

Let c be a partial edge-colouring of G. We denote the set of colours in c by C = {1, 2, . . . , k}. For any vertex u ∈ V (G), we define F u (c) = {c(uz) | z ∈ N G (u)}, with N G (u) denotes the set of vertices adjacent tot u. For an edge ab ∈ E, we define S ab (c) = F b (c) -{c(ab)}. Note that S ab (c) need not be the same as S ba (c). We will abbreviate the notation to F u and S ab when the edge-colouring c is understood from the context.

The following definitions arise out of our attempt to understand what may prevent us from extending a partial edge-colouring of G \ e to G.

Maximal bichromatic Path:. An (α,β)-maximal bichromatic path with respect to a partial edgecolouring c of G is a maximal path consisting of edges that are coloured using the colours α and β alternatingly. An (α,β,a,b)-maximal bichromatic path is an (α,β)-maximal bichromatic path which starts at the vertex a with an edge coloured α and ends at b. We emphasize that the edge of the (α,β,a,b)maximal bichromatic path incident on vertex a is coloured α and the edge incident on vertex b can be coloured either α or β. Thus the notations (α,β,a,b) and (α,β,b,a) have different meanings. Also note that any maximal bichromatic path will have at least two edges. The following fact is obvious from the definition of proper edge-colouring.

Fact 2.3. Given a pair of colours α and β of a proper edge-colouring c of G, there is at most one maximal (α,β)-bichromatic path containing a particular vertex v, with respect to c.

A colour α = c(e) is a candidate for an edge e in G with respect to a partial edge-colouring c of G if none of the adjacent edges of e is coloured α. A candidate colour α is valid for an edge e if assigning the colour α to e does not result in any bichromatic cycle in G.

Let e = ab be an edge in G. Note that any colour β / ∈ F a ∪ F b is a candidate colour for the edge ab in G with respect to the partial edge-colouring c of G. A sufficient condition for a candidate colour being valid is captured in the lemma below.

Lemma 2.4 (Basavaraju and Chandran [START_REF] Basavaraju | Acyclic edge coloring of graphs with maximum degree 4[END_REF]). A candidate colour for an edge e = ab is valid if

(F a (c) ∩ F b (c)) \ {c(ab)} = S ab (c) ∩ S ba (c) = ∅.
Now even if S ab (c) ∩ S ba (c) = ∅, a candidate colour β may be valid. But if β is not valid, then what may be the reason? It is clear that colour β is not valid if and only if there exists α = β such that a (α,β)-bichromatic cycle gets formed if we assign colour β to the edge e. In other words, if and only if, with respect to edge-colouring c of G there existed an (α, β, a, b)-maximal bichromatic path with α being the colour given to the first and last edge of this path. Such paths play an important role in our proofs. We call them critical paths. It is formally defined below.

Critical Path:. Let ab ∈ E and c be a partial edge-colouring of G. Then an (α, β, a, b)-maximal bichromatic path which starts out from the vertex a via an edge coloured α and ends at the vertex b via an edge coloured α is called an (α, β, a, b)-critical path. Note that any critical path will be of odd length. Moreover the smallest length possible is three.

Let a ∈ N G\vv1 (x) and let c(x, a) = α. Let β ∈ S xa . colour β is said to be actively present in a set S xa , if there exists a (α, β, xy) critical path.

A natural strategy to extend a acyclic partial edge-colouring c of G would be to try to assign one of the candidate colours to an uncoloured edge e. The condition that a candidate colour is not valid for the edge e is captured in the following fact.

Fact 2.5. Let c be a partial edge-colouring of G. A candidate colour β is not valid for the edge e = ab if and only if for some colour α ∈ S ab ∩ S ba , there is an (α, β, a, b)-critical path in G with respect to c. Colour exchange:. Let c be a partial edge-colouring of G. Let u, v, w ∈ V (G) and uv, uw ∈ E(G). We define colour exchange with respect to the edge uv and uw, as the modification of the current partial edge-colouring c by exchanging the colours of the edges uv and uw to get a partial edge-colouring c , i.e., c (uv) = c(uw), c (uw) = c(uv) and c (e) = c(e) for all other edges e in G. The colour exchange with respect to the edges uv and uw is said to be proper (resp. acyclic) if the edge-colouring obtained after the exchange is proper (resp. acyclic). The following fact is obvious.

Fact 2.6. Let c be the partial edge-colouring obtained from an acyclic partial edge-colouring c by the colour exchange with respect to the edges uv and uw. Then c is proper if and only if c(uv) / ∈ S uw and c(uw) / ∈ S uv . The colour exchange is useful in breaking some critical paths as is clear from the following lemma.

Lemma 2.7 (Basavaraju and Chandran [START_REF] Basavaraju | Acyclic edge coloring of graphs with maximum degree 4[END_REF][START_REF] Basavaraju | Acyclic edge coloring of 2-degenerate graphs[END_REF]). Let u, v, w, a and b be vertices of G such that uv, uw and ab are edges. Also let α and β be two colours such that {α, β} ∩ {c(uv), c(uw)} = ∅ and {v, w} ∩ {a, b} = ∅. Suppose there exists a (α, β, a, b)-critical path that contains vertex u, with respect to an acyclic partial edge-colouring c of G. Let c be the partial edge-colouring obtained from c by the colour exchange with respect to the edges uv and uw. If c is proper, then there is no (α, β, a, b)-critical path in G with respect to c .

Multisets and Multiset Operations:. Recall that a multiset is a generalized set where a member can appear multiple times. If an element x appears t times in the multiset S, then we say that the multiplicity of x in S is t. In notation mult S (x) = t. The cardinality of a finite multiset S, denoted by S , is defined as S = x∈S mult S (x). Let S 1 and S 2 be two multisets. The reader may note that there are various possible ways to define union of S 1 and S 2 . For the purpose of this paper we define one such union notion-which we call as the join of S 1 and S 2 , denoted as S 1 S 2 . The multiset S 1 S 2 have all the members of S 1 as well as S 2 . For a member

x ∈ S 1 S 2 , mult S1 S2 (x) = mult S1 (x) + mult S2 (x). Clearly S 1 S 2 = S 1 + S 2 .
2.2. There exists a Configuration A2, A3 or A4. We now can resume the proof of Theorem 2.1. Suppose by way of contradiction that there exists a Configuration A 2 , A 3 or A 4 in G. Let v, v 1 , v 2 and v 3 be the vertices as described in Lemma 2.2.

In all the propositions of this subsection, we start with an acyclic edge-colouring c of G \ vv 1 . So the abbreviations F u and S ab stand for F u (c ) and S ab (c ) respectively.

Proposition 2.8. For any acyclic edge-colouring

c of G \ vv 1 , |F v ∩ F v1 | ≥ 2.
Proof. Suppose by way of contradiction that there is an acyclic edge-colouring

c of G \ vv 1 with a set C of ∆ + 12 colours such that |F v ∩ F v1 | ≤ 1. Assume first that |F v ∩ F v1 | = 0.
The reader can verify from close examination of Configurations A2, A3 and A4 that |F v ∪ F v1 | will be maximum for Configuration A2 and therefore

|F v ∪ F v1 | = |F v | + |F v1 | ≤ 2 + 10 = 12.
Thus there are ∆ candidate colours for the edge vv 1 and by Lemma 2.4 all the candidate colours are valid, a contradiction to the assumption that G is a counter-example.

Assume now that

|F v ∩ F v1 | = 1. It is easy to see that |F v ∪ F v1 | = |F v | + |F v1 | -|F v ∩ F v1 | ≤ 11
and hence there are at least ∆ + 1 candidate colours for the edge vv 1 . Let F v ∩ F v1 = {α} and let u ∈ N (v) be a vertex such that c (vu) = α. Now if none of the ∆ + 1 candidate colours is valid for the edge vv 1 , then by Fact 2.5, for each γ ∈ C \ (F v ∪ F v1 ), there exists an (α, γ, v, v 1 )-critical path. Since c (vu) = α, we have all the critical paths passing through the vertex u and hence

S vu ⊆ C \ (F v ∪ F v1 ). This implies that |S vu | ≥ |C \ (F v ∪ F v1 )| ≥ (∆ + 12) -11 = ∆ + 1, a contradiction since |S vu | ≤ ∆ -1.
Thus we have a valid colour for the edge vv 1 , a contradiction to the assumption that G is a counter-example.

Let S v be the multiset defined by S v = S vv2 S vv3 . . . S vv k . Proposition 2.9. For any acyclic edge-colouring

c of G \ vv 1 , |F v ∩ F v1 | = 2. Proof. Suppose not. Let F v ∩ F v1 = {α 1 , α 2 } and let v , v ∈ N G\vv1 (v) and u , u ∈ N G\vv1 (v 1 ) be such that c (vv ) = c (v 1 u ) = α 1 and c (vv ) = c (v 1 u ) = α 2 . It is easy to see that |F v ∪ F v1 | ≤ 10.
Thus there are at least ∆ + 2 candidate colours for the edge vv 1 . If any of the candidate colours is valid for the edge vv 1 , we are done. Thus none of the candidate colours is valid for the edge vv 1 . This implies that there exists a (α 1 , θ, v, v 1 )-or (α 2 , θ, v, v 1 )-critical path for each candidate colour θ.

Claim 1. The multiset S v contains at least |F v1 | -1 colours from F v1 . Proof. Suppose not. Then there are at least two colours in F v1 which are not in S v . Let ν and µ be any two such colours. Now assign colours ν and µ to the edges vv and vv respectively to get an edge-colouring c . Now since ν, µ / ∈ S v , we have ν / ∈ S vv and µ / ∈ S vv . Moreover µ, ν / ∈ F v (c ) \ {α 1 , α 2 }. Thus the edge-colouring c is proper. Now we claim that the edge-colouring c is acyclic also. Suppose not. Then there has to be a bichromatic cycle containing at least one of the colours ν and µ. Clearly this cannot be a (ν, µ)-bichromatic cycle since µ / ∈ S vv . Therefore it has to be a (ν, λ)-or (µ, λ)-bichromatic cycle where λ ∈ F v (c ) \ {ν, µ}. Let u be a vertex such that c (vu) = λ. This means that there was already a (λ, ν, v, v )-or (λ, µ, v, v )-critical path with respect to the edge-colouring c . This implies that

ν ∈ S vu or µ ∈ S vu , implying that ν ∈ S v or µ ∈ S v , a contradiction. Thus the edge-colouring c is acyclic. Let u 1 , u 2 ∈ N G\vv1 (v 1 ) be such that c (v 1 u 1 ) = ν and c (v 1 u 2 ) = µ. Note that |F v ∪ F v1 | ≤ 10 (The maximum value of |F v ∪ F v1
| is attained when the graph has Configuration A2). Therefore there are at least ∆ + 2 candidate colours for the edge vv 1 . If any of the candidate colours are valid for the edge vv 1 , then we are done as this is a contradiction to the assumption that G is a counter-example. Thus none of the candidate colours is valid for the edge vv 1 and therefore there exist either a (ν, θ, v, v 1 )-critical or a (µ, θ, v, v 1 )-critical path for each candidate colour θ. Let C ν and C µ respectively be the set of candidate colours which are forming critical paths with colours ν and µ. Then clearly C ν ⊆ S v1u1 and C µ ⊆ S v1u2 since c (v 1 u 1 ) = ν and c (v 1 u 2 ) = µ. Now we exchange the colours of the edges vv and vv to get a modified edge-colouring c. Note that c is proper since µ / ∈ S vv and ν / ∈ S vv . By Lemma 2.7, all (ν, β, v, v 1 )-critical paths where β ∈ C ν and all (µ, γ, v, v 1 )-critical paths where γ ∈ C µ are broken. Now if none of the colours in C ν are valid for edge vv 1 , then it means that for each β ∈ C ν , there exists a (µ, β, v, v 1 )-critical path with respect to the edge-colouring c, implying that C ν ⊆ S v1u2 . Since the recolouring involved no candidate colours, we still have

C µ ⊆ S v1u2 . Thus we have (C ν ∪ C µ ) ⊆ S v1u2 . But |C ν ∪ C µ | ≥ ∆ + 2 which implies that |S v1u2 | ≥ ∆ + 2, a contradiction since |S v1u2 | ≤ ∆ -1.
Claim 2. There exists at least two colours β 1 and β 2 in C \ F v1 with multiplicity at most one in S v .

Proof. In view of Claim 1 we have •

x∈C\Fv mult Sv (x) = S v -(|F v | -1). Thus if S v -(|F v1 | -1) ≤ 2|(C \ F v1 )| -3,
For A2, S v +|F v1 | ≤ (d(v 2 ) -1) + (d(v 3 ) -1) + |F v1 | = (∆ -1) + (∆ -1) + 10 = 2∆ + 8. • For A3, S v +|F v1 | ≤ (d(v 2 )-1)+(d(v 3 )-1)+(d(v 4 )-1)+|F v1 | = 10+(∆-1)+(∆-1) +6 = 2∆ + 14. • For A4, S v +|F v1 | ≤ (d(v 2 ) -1) + (d(v 3 ) -1) + (d(v 4 ) -1) + (d(v 5 ) -1) + |F v1 | = 6 + 10 + (∆ -1) + (∆ -1) + 5 = 2∆ + 19.
The colours β 1 and β 2 of Claim 2 are crucial to the proof. Now we make another claim regarding β 1 and

β 2 : Claim 3. β 1 and β 2 ∈ F v .
Proof. Without loss of generality, let β 1 / ∈ F v . Then recalling that β 1 / ∈ F v1 , β 1 is a candidate for the edge vv 1 . If it is not valid, then there exists either an (α 1 , β 1 , vv 1 )-or (α 2 , β 1 , v, v 1 )-critical path with respect to c . Since the multiplicity of β 1 in S v is at most one, we have the colour β 1 in exactly one of S vv or S vv . Without loss of generality let β 1 ∈ S vv . Hence there exists an (α 2 , β 1 , v, v 1 )-critical path with respect to c . Now recolour the edge vv with colour β 1 to get an edge-colouring c. Then c is proper since β 1 / ∈ F v and β 1 / ∈ S vv . We shall prove that is is acyclic. Suppose, by way of contradiction, that there is a bichromatic cycle with respect to c. Then it has to be a (β 1 , γ)-bichromatic cycle for some γ ∈ F v (c) \ c(vv ). Let a ∈ N G\vv1 (v) be such that c(va) = γ. Then the (β 1 , γ)-bichromatic cycle should contain the edge va and therefore γ ∈ S va (c). But we know that v is the only vertex in N G\vv1 (v) such that β 1 ∈ S vv . Therefore a = v . This implies that γ = α 2 and there existed an (α 2 , β 1 , v, v )-critical path with respect to the edge-colouring c . This is a contradiction to Fact 2. ∈ S vv and α 1 / ∈ S vv (Recall that S vv and S vv contain only candidate colours). We shall prove that c is also acyclic: A bichromatic cycle with respect to c has to be an (α 1 , η)-or (α 2 , η)-bichromatic cycle for some η ∈ F v . Clearly it cannot be an (α 1 , α 2 )bichromatic cycle since α 1 / ∈ S vv (c) and therefore η ∈ {β 1 , β 2 } (Recall that

F v = {α 1 , α 2 , β 1 , β 2 }
). This implies that either β 1 or β 2 belongs to S vv ∪ S vv . But we know that S vv ∪ S vv is exactly the set of candidate colours for the edge vv 1 , a contradiction since β 1 , β 2 ∈ F v cannot be candidate colours for the edge vv 1 .

Therefore the edge-colouring c is acyclic. By Lemma 2.7, all the existing critical paths are broken. Now consider a colour γ ∈ S vv . If it is still not valid then there has to be a (α 2 , γ, v, v 1 )-critical path since c(vv ) = α 2 and γ / ∈ S vv (c). This implies that γ ∈ S v1u (c), a contradiction since S v1u (c) ∩ S vv (c) = ∅. Thus we have a valid colour for the edge vv 1 , a contradiction to the assumption that G is a counterexample.

From Claim 4, we infer that c (vv

2 ) / ∈ F v ∩F v1 since F v ∩F v1 = {c (vv ), c(vv )} = {α 1 , α 2 }. Therefore we have c(vv 2 ) ∈ {β 1 , β 2 } since F v = {α 1 , α 2 , β 1 , β 2 }.
Without loss of generality let c(vv 2 ) = β 1 . We know that the colour β 2 can be in at most one of S vv and S vv by Claim 2. Now let v be such that

β 2 / ∈ S vv . Note that C \ (S vv ∪ F v ∪ F v1 ) = ∅ since |S vv ∪ F v ∪ F v1 | ≤ ∆ -1 + 4 + 5 -2 = ∆ + 6. Assign a colour θ ∈ C \ (S vv ∪ F v ∪ F v1 ) to the edge vv to get an edge-colouring c . Now |F v (c ) ∩ F v1 (c )| = 1.
Thus in view of Proposition 2.8, the edge-coloring c is not acyclic. Hence there is a bichromatic cycle with respect to c . This bichromatic cycle should involve one of the colours α 2 , β 1 , β 2 along with θ. Since the bichromatic cycle contains a colour from S vv and β 2 / ∈ S vv , it cannot be a (θ, β 2 )-bichromatic cycle. Now with respect to the edge-colouring c , colour θ was not valid for the edge vv 1 implying that there existed a (α 1 , θ, v, v 1 )-or (α 2 , θ, v, v 1 )-critical path. But (α 1 , θ, v, v 1 )-critical path was not possible since θ / ∈ S vv by the choice of θ. Thus there existed an (α 2 , θ, v, v 1 )-critical path with respect to c . Thus by Fact 2.3, there cannot be an (α 2 , θ, v, v )-critical path with respect to c and hence there cannot be an (α 2 , θ)-bichromatic cycle in c formed due to the recolouring. Thus if there is a bichromatic cycle formed, then it has to be a (β 1 , θ)-bichromatic cycle, which implies that β 1 ∈ S vv . Now taking into account the fact that β 1 is in S vv as well as F v , we get

|S vv ∪ F v ∪ F v1 | ≤ ∆ -1 + 4 + 5 -2 -1 = ∆ + 5 and therefore |S vv ∪ F v ∪ F v1 ∪ S vv2 | ≤ ∆ + 5 + 6 = ∆ + 11. Thus C \ (S vv ∪ F v ∪ F v1 ∪ S vv2 ) = ∅. Now recolour the edge vv using a colour γ ∈ C \ (S vv ∪ F v ∪ F v1 ∪ S vv2 )
to get an edge-colouring c. Clearly this edge-colouring is proper. It is also acyclic since if a bichromatic cycle gets formed it has to be a (β 1 , γ) bichromatic cycle (Note that the (α 2 , γ) and (β 2 , γ) bichromatic cycles are argued out as before). But γ / ∈ S vv2 , a contradiction. Thus the edge-colouring c is acyclic.

But |F v (c) ∩ F v1 (c)| = 1,
S v = S v \(F v1 ∪F v . Let v , v , v ∈ N G\vv1 (v) be such that {c(vv ), c(vv ), c(vv )} = F v ∩F v1 . Also let c(vv ) = α 1 , c(vv ) = α 2 and c(vv ) = α 3 . Claim 5. S v ≤ 2∆ + 11. Proof. When d(v) = 4, it is clear that S v ≤ (d(v 2 )-1)+(d(v 3 )-1)+(d(v 4 )-1) ≤ 10+∆-1+∆-1 = 2∆ + 8.
On the other hand when d(v) = 5, try to recolour one of the edges vv , vv , vv using a colour in C \ (F v ∪ F v1 ). There are ∆ + 6 colours in C \ (F v ∪ F v1 ). If any of these colours is valid for one of vv , vv or vv , then recolouring this edge with this colour, we obtain an acyclic edge-colouring c satisfying |F v (c )∩F v1 (c )| = 2. This contradicts Proposition 2.9. Hence there has to be a bichromatic cycle formed during each recolouring. Since such a bichromatic cycle has to be a (γ 1 , γ 2 )-bichromatic cycle where γ 1 is the colour used in the recolouring and γ 2 ∈ F v \{γ 1 }, we infer that S vv , S vv and S vv contain at least one colour from F v . Thus we have

S v ≤ S v -3 ≤ (d(v 2 )-1)+(d(v 3 )-1)+(d(v 4 )-1)+(d(v 5 )-1)-3 ≤ 6 + 10 + ∆ -1 + ∆ -1 -3 = 2∆ + 11.
Claim 6. There exists at least one colour β ∈ C \ (F v ∪ F v1 ) with multiplicity at most one in S v .

Proof. Since v belongs to either configuration A3 or configuration A4, we have

|F v ∪ F v1 | ≤ 9 -3 = 6. Thus |C \ (F v ∪ F v1 )| ≤ ∆ + 6
. By Claim 5 we have S v ≤ 2∆ + 11 and from this it is easy to see that there exists at least one colour β ∈ C \ (F v ∪ F v1 ) with multiplicity at most one in S v .

Note that β ∈ C \ (F v ∪ F v1 ), where β is the colour from Claim 6 is a candidate colour for the edge vv 1 . If it is not valid then there has to be a (θ, β, v, v 1 )-critical path, where θ ∈ {α 1 , α 2 , α 3 }. By Claim 6, β can be present in at most one of S vv , S vv and S vv . Without loss of generality let β ∈ S vv . Thus there exists an (α 2 , β, v, v 1 )-critical path with respect to the edge-colouring c . Recolour the edge vv using the colour β to get an edge-colouring c. Clearly c is proper since β / ∈ S vv and β / ∈ F v . Let us show that it is also acyclic. A bichromatic cycle (with respect to c) has to contain the colour β as well as a colour γ ∈ F v (c) \ {β}. If γ = c(vw), then β ∈ S vw , for the (β, γ)-bichromatic cycle to get formed. But v is the only vertex in N G\vv1 (v) such that β ∈ S vv . Thus w = v , γ = α 2 and the cycle is an (α 2 , β)-bichromatic cycle. This means that there existed an (α 2 , β, v, v )-critical path with respect to the edge-colouring c , a contradiction to Fact 2.3 since there already existed an (α 2 , β, v, v 1 )-critical path with respect to the edge-colouring c . Thus the edge-colouring c is acyclic.

But |F v (c) ∩ F v1 (c)| = 2, a contradiction to Proposition 2.9. This completes the proof of Proposition 2.10.

Proposition 2.11. For any acyclic edge-colouring

c of G \ vv 1 , |F v ∩ F v1 | = 4. Proof. Suppose not. Let c be an acyclic edge-colouring of G \ vv 1 such that |F v ∩ F v1 | = 4. Then |F v | ≥ 4 and since d(v) ≤ 5, we have d(v) = 5. Hence v belongs to Configuration A4. Let S v be the multiset defined by S v = S v \ (F v1 ∪ F v ). Also let c(vv 2 ) = α 1 , c(vv 3 ) = α 2 , c(vv 4 ) = α 3 and c(vv 5 ) = α 4 .
Now try to recolour an edge incident on v with a candidate colour from C \ (F v ∪ F v1 ). If the obtained edge-colouring c is acyclic then |F v (c ) ∩ F v1 (c )| = 3, a contradiction to Proposition 2.10. Hence there has to be a bichromatic cycle created due to recolouring with one of the colours from F v . This implies that

F v ∩ S v = ∅. Thus we have S v ≤ S v -1 ≤ (d(v 2 ) -1) + (d(v 3 ) -1) + (d(v 4 ) -1) + (d(v 5 ) -1) ≤ 6 + 10 + ∆ -1 + ∆ -1 -1 = 2∆ + 13. Now since there are |C \ (F v ∪ F v1 )| ≥ ∆ + 12 -(4 + 5 -4) = ∆ + 7
candidate colours and S v ≤ 2∆ + 13, it is easy to see that there exists at least one candidate colour β with multiplicity at most one in S v .

Note that β ∈ C \ (F v ∪ F v1 ) is a candidate colour for the edge vv 1 . If it is not valid then there has to be a (θ, β, v, v 1 )-critical path, where θ ∈ {α 1 , α 2 , α 3 , α 4 }. We know that β can be present in at most one of S vv2 , S vv3 , S vv4 and S vv5 . Without loss of generality let β ∈ S vv3 . Thus there exists an (α 2 , β, v, v 1 )-critical path with respect to the edge-colouring c . Recolour the edge vv 2 using the colour β to get an edge-colouring c. Clearly c is proper since β / ∈ S vv2 and β / ∈ F v . Let us now show that it is acyclic. A bichromatic cycle with respect to c has to contain the colour β as well as a colour γ ∈ F v (c) \ {β}. If γ = c(vw), then β ∈ S vw , for the (β, γ) bichromatic cycle to get formed. But v 3 is the only vertex in N G\vv1 (v) such that β ∈ S vv3 . Thus w = v 3 , γ = α 2 and it has to be a (β, α 2 ) bichromatic cycle. This means that there existed an (α 2 , β, v, v 2 )-critical path with respect to the edge-colouring c , a contradiction to Fact 2.3 since there already existed an (α 2 , β, v, v 1 )-critical path with respect to the edge-colouring c . Thus the edge-colouring c is acyclic.

But |F v (c) ∩ F v1 (c)| = 3, a contradiction to Proposition 2.10. By Lemma 2.2, d G\vv1 (v) ≤ 4. Thus |F v ∩ F v1 | ≤ |F v | ≤ 4.
Then Propositions 2.8, 2.9, 2.10 and 2.11 gives a contradiction to the assumption that G contains a Configuration A2, A3 or A4.

2.3.

There is no Configuration A2, A3 or A4. In the previous subsection, we showed that G contains no Configuration A2, A3 or A4. Then by Lemma 2.2, there is a Configuration A1, that is a vertex v such that d(v) = 2. Now delete all the degree 2 vertices from G to get a graph H. Now since the graph H is also planar, there exists a vertex v in H such that v belongs to one of the configurations A1, A2, A3 or A4, say A . The vertex v was not already in Configuration A in G. This means that the degree of at least one of the vertices of the configuration A i.e., {v } ∪ N H (v ), got decreased by the removal of 2-degree vertices. Let P = {x ∈ {v } ∪ N H (v ) : d H (x) < d G (x)}. Let u be the minimum degree vertex in P in the graph H. Now it is easy to see that d H (u) ≤ 11 since v did not belong to A in G.

Let Let us now consider the edge-colouring c. Let a ∈ N (u) be such that c(ua) = c(u u ) = α. Now if none of the candidate colours in C \ (F u ∪ F u ) are valid for the edge uu , then by Fact 2.5, for each γ ∈ C \ (F u ∪ F u ), there exists an (α, γ, u, u )-critical path. Since c (ua) = α, we have all the critical paths passing through the vertex a and hence

N (u) = {x|x ∈ N G (u) and d G (u) = 2}. Let N (u) = N G (u) -N (u). It is obvious that N (u) = N H (u).
S ua ⊆ C \ (F u ∪ F u ). This implies that |S ua | ≥ |C \ (F u ∪ F u )| ≥ ∆ + 12 -(1 + ∆ -1 -1) = 13, a contradiction since |S ua | = 1.
Thus we have a valid colour for the edge uu , a contradiction to the assumption that G is a counter-example.

This final contradiction completes the proof of Theorem 2.1.

3. Planar graphs of girth at least 5. The aim of this section is to prove Conjecture 1.2 for planar graphs of girth at least 5. Actually, we prove the conjecture for a more general class of graphs: the graphs of maximum average degree at most 10/3. The average degree of a graph G is Ad

(G) = 1 |V (G)| v∈V (G) d(v) = 2|E(G)| |V (G)| . The maximum average degree of G is M ad(G) = max{Ad(H) | H is a subgraph of G}.
It is well known that the girth and the maximum average degree of a planar graph are related to each other: Proposition 3.1. Let G be a planar graph of girth g. M ad(G) < 2 + 4 g -2 .

Theorem 3.2. Let ∆ ≥ 19 and G be a graph with maximum degree at most ∆ and maximum average degree less than 10 3 . Then χ a (G) ≤ ∆. Theorem 3.2 and Proposition 3.1 immediately yield the following. Corollary 3.3. Let ∆ ≥ 19 and G be a planar graph with maximum degree at most ∆ and girth at least 5. Then χ a (G) ≤ ∆.

More generally than Theorem 3.2, we show the following. Theorem 3.4. For any > 0, there exists an integer ∆ such that every graph G with maximum degree at most ∆ with ∆ ≥ ∆ and maximum average degree less than 4 -is acyclically ∆-edgecolourable.

In order to prove Theorems 3.2 and 3.4, we first establish some properties of ∆-minimal graphs which are graphs with maximum degree at most ∆, not acyclically ∆-edge-colourable but such that every proper subgraph is. Then, by the Discharging Method, we deduce that such a graph has maximum average degree at least 4 -(resp. 10/3) if ∆ is at least ∆ (resp. [START_REF] Nešetřil | The acyclic edge chromatic number of a random d-regular graph is d + 1[END_REF]). We will first prove, in Subsection 3.2, Theorem 3.4 for its discharging procedure is simpler because we only establish the existence of ∆ and make no attempt to minimize it. We then show Theorem 3.2 in Subsection 3.3.

A vertex of degree i is called an i-vertex and an i-neighbour of a vertex v is a neighbour of v having degree i.

Properties of

∆-minimal graphs. Proposition 3.5. A ∆-minimal graph G is 2-connected. In particular, δ(G) ≥ 2.
Proof. If G is not connected, it is the disjoint union of G 1 and G 2 . Both G 1 and G 2 admits an acyclic ∆-edge-colouring by minimality of G. The union of these two edge-colourings is an acyclic ∆edge-colouring of G.

Suppose now that G has a cutvertex v. Let C i , for 1 ≤ i ≤ p be the components of G -v and G i the graph induced by C i ∪ {v}. By minimality of G, all the G i admit an acyclic ∆-edge-colouring. Moreover, free to permute the colours we may assume that two edges incident to v get different colours. Hence the union of these edge-colourings is an acyclic ∆-edge-colouring of G because any cycle of G is entirely contained in one of the G i .

Proposition 3.6. Let G be a ∆-minimal graph. For every vertex v ∈ V (G), u∈N (v) d(u) ≥ ∆+1.

Proof. Suppose by way of contradiction that there is a vertex v such that u∈N (v) d(u) ≤ ∆. Let w be a neighbour of v. By minimality of G, G \ vw admits an acyclic edge-colouring with ∆ colours. Now colour vw with a colour distinct from the ones of the edges incident to a neighbour of v. This is possible as there are at most ∆ -1 such edges distinct from vw. Doing so we clearly obtain a proper edge-colouring. Let us now show that there is no bicoloured cycle. A cycle that does not contain vw has edges of at least three colours as the edge-colouring of G was acyclic and a cycle containing vw must contain an edge vu and an edge tu with u ∈ N (v) \ {w}. By construction, the colours of tu, uv and vw are distinct.

A thread is a path of length two whose internal vertex has degree 2. Proposition 3.7. Let k ≥ 2 be an integer and G a ∆-minimal graph. In G, a ∆-vertex is the end of at most k threads whose other endvertex has degree at most k.

To prove this proposition we need the following lemma. Lemma 3.8. Let H = ((A, B), E) be a bipartite graph with |A| = |B| = q such that for any vertex a ∈ A d(a) = 1 and let K A,B be the complete bipartite graph with bipartition (A, B). If at least 3 vertices of B of degree at least one in H then there exists a perfect matching M of K A,B such that the bipartite graph ((A, B), E ∪ M ) has girth at least 6.

Proof. Let m be the number of vertices of B of degree at least one. Let b 1 , . . . , b q be the vertices of B with d(b i ) ≥ 1 if i ≤ m and d(b i ) = 0 otherwise. And let a 1 , . . . , a q be the vertices of A with a

i b i ∈ E for all 1 ≤ i ≤ m. If m ≥ 3, let M = {a i b i+1 | 1 ≤ i < m} ∪ {a m b 1 } ∪ {a i b i | m < i ≤ q}. Then the unique cycle in ((A, B), E ∪ M ) is C = (a 1 , b 2 , a 2 , b 3 , . . . , a m-1 , b m , a 1 ). It has length 2m ≥ 6.
Proof. [ of Proposition 3.7] Suppose for a contradiction that there is a ∆-vertex u with q = k + 1 threads uv i w i , 1 ≤ i ≤ q, such d(w i ) ≤ k. Note that q ≥ 3.

Set A = {v 1 , . . . , v q }. By Proposition 3.5, w i / ∈ A for all 1 ≤ i ≤ q. By minimality of G, G -A admits an acyclic ∆-edge-colouring.

Let us first extend it to the v i w i as follows. Let F be the set of colours assigned to the edges incident to u and to no vertex of A and for 1 ≤ i ≤ q let F i be the set of colours assigned to the edges incident to w i (and distinct from

v i w i ). Then |F | = ∆ -q and |F i | ≤ k -1. For all 1 ≤ i ≤ q, let S i be the set of colours not in F ∪ F i . Since |F | + |F i | = ∆ -q + k -1 = ∆ -2 then |S i | ≥ 2.
. Assume first that | q i=1 S i | ≥ 3, then one can assign to each v i w i a colour in S i in such a way that at least 3 colours appear on such edges and that different colours appear on v i w i and v j w j ifw i = w j . We will now colour the edges uv i for 1 ≤ i ≤ q. Therefore let H 1 = ((A, B), E 1 ) be the bipartite graph with B the set of q colours {b 1 , . . . , b q } not in F and in which v i is adjacent to b j if c(v i w i ) = b j . As long as some v i has degree 0 then add an edge between a i and an isolated b j to obtain a bipartite graph H 2 = ((A, B), E 2 ). Because at least three colours appear on the v i w i , the graph H 2 fulfils the hypothesis of Lemma 3.8. So there exists a perfect matching M of K A,B such that ((A, B), E 2 ∪ M ) has girth at least 6. For 1 ≤ i ≤ q, assign to each uv i the colour to which v i is linked in M .

Let us now prove that this edge-colouring of G is acyclic. It is obvious that it is proper since v i is not linked to c(v i w i ) in M . Let us now prove that it is acyclic. Let C be a cycle of G. If it contains no vertex of A, then it contains edges of three different colours because the edge-colouring of G -A is acyclic. Suppose now that C contains a unique vertex of A, say v i . Then C contains w i v i , v i u and ut with t a neighbour of u not in A. Then c(ut) ∈ F , so by construction, c(w i v i ) = c(ut). Hence the colours of w i v i , v i u and ut are distinct. Suppose finally that C contains two vertices of A, say v i and v j . Then C contains w i v i , v i u, w j v j and v j u. Since ((A, B), E 2 ∪ M ) has girth at least 6, either c(v i u) = c(w j v j ) or c(v j u) = c(w i v i ). In both cases, C has edges of three different colours.

. Asumme now that | q i=1 S i | < 3. Then all the S i are equal and of cardinality 2, say S i = {a, b} for all 1 ≤ i ≤ q. Hence all the F i are the same of cardinality k -1 and disjoint from F . Observe that this can happen only if all the w i are distinct. Let us denote by f 1 , . . . , , f k-1 the elements of the F i . Let us set c(v i w i ) = a for 1 ≤ i ≤ k, c(v q w q ) = b, c(uv i ) = f i for 1 ≤ i ≤ k -1, c(uv k ) = b and c(uv k+1 ) = a. It is easy to check that the obtained edge-colouring is an acyclic edge-colouring of G. Proposition 3.9. Let k and l be two positive integers and G a ∆-minimal graph. In G, a (∆ -l)vertex is the end of at most k -1 -l threads whose other endvertex has degree at most k.

To prove this proposition we need the following lemma. Lemma 3.10. Let H = ((A, B), E) be a bipartite graph with q = |A| < |B| such that for any vertex a ∈ A d(a) = 1 and K A,B be the complete bipartite graph with bipartition (A, B).

Then there exists a matching M of K A,B saturating A such that the bipartite graph ((A, B), E ∪ M ) has no cycle.

Proof. Let q = |B|. Let b 1 , . . . , b q be the vertices of B with d(b i ) ≥ 1 if i ≤ m and d(b i ) = 0 otherwise. And let a 1 , . . . , a q be the vertices of A with a i b i ∈ E for all 1 ≤ i ≤ m. Let M = {a i b i+1 | 1 ≤ i ≤ q}. This is well-defined since q > q. Then ((A, B), E ∪ M ) has no cycle.

Proof. [ of Proposition 3.9]. Suppose for a contradiction that there is a (∆ -l)-vertex u with q = k -l threads uv i w i , 1 ≤ i ≤ q, such d(w i ) ≤ k.

Set A = {v 1 , . . . , v q }. By minimality of G, G -A admits an acyclic ∆-edge-colouring. Let us first extend it to the v i w i as follows. Let F be the set of colours assigned to the edges incident to u and to no vertex of A and for 1 ≤ i ≤ q let F i be the set of colours assigned to the edges incident to w i (and

  then there exist at least two colours β 1 and β 2 in C \ F v1 with multiplicity at most one in S v . Thus it is enough to prove S v ≤ 2|C|-|F v1 |-4 ≤ 2∆+24-|F v1 |-4 = 2∆+20-|F v1 |. Now we can easily verify that S v +|F v1 | ≤ 2∆ + 20 for Configurations A2, A3 and A4 as follows:

  3 since there already existed an (α 2 , β 1 , v, v 1 )-critical path with respect to the edge-colouring c .Thus the edge-colouring c is acyclic and|F v (c) ∩ F v1 (c)| = 1, a contradiction to Proposition 2.8. Note that {β 1 , β 2 }∩{α 1 , α 2 } = ∅ since β 1 , β 2 / ∈ F v1 . In view of Claim 3, we have {α 1 , α 2 , β 1 , β 2 } ⊆ F v and thus |F v | ≥ 4, which implies that d(v) ≥ 5. Thus the vertex v belongs to Configuration A4. Therefore d(v) = 5 and F v = {α 1 , α 2 , β 1 , β 2 }. There are at least ∆ + 12 -(5 + 4 -2) = ∆ + 5 candidate colours for the edge vv 1 . Also recall that d(v 2 ) ≤ 7, c (vv ) = c (v 1 u ) = α 1 and c (vv ) = c (v 1 u ) = α 2 .Claim 4. v 2 / ∈ {v , v }. Proof. Suppose not. Then, without loss of generality, v 2 = v and c (vv 2 ) = α 1 . Now if none of the ∆ + 5 candidate colours is valid for the edge vv 1 , then they all are in critical paths that contain either the edge vv or the edge vv . Now |S vv | + |S vv | ≤ 6 + ∆ -1 = ∆ + 5. Since each of the ∆ + 5 candidate colours has to be present in either in S vv or S vv , we infer that S vv ∪ S vv is exactly the set of candidate colours, i.e., |S vv | + |S vv | = ∆ + 5. This requires that |S vv | = 6, |S vv | = ∆ -1 and S vv ∩ S vv = ∅. Since for each γ ∈ S vv , we have (α 2 , γ, v, v 1 )-critical path containing u , we can infer that S vv ⊆ S v1u (Recall that c (v 1 u ) = α 2 ). But since |S v1u | ≤ ∆ -1, we have S vv = S v1u . Thus S v1u ∩ S vv = S vv ∩ S vv = ∅. Now we exchange the colours of the edges vv and vv to get an edge-colouring c. Hence c(vv ) = α 2 and c(vv ) = α 1 . The edge-colouring c is proper since α 2 /

  a contradiction to Proposition 2.8. This completes the proof of Proposition 2.9. Proposition 2.10. For any acyclic edge-colouring c of G \ vv 1 , |F v ∩ F v1 | = 3. Proof. Suppose not. Let c be an acyclic edge-colouring of G \ vv 1 such that |F v ∩ F v1 | = 3. Then |F v | ≥ 3 and therefore d(v) ≥ 4. Thus v belongs to either configuration A3 or A4. Let S v be the multiset defined by

  Since u ∈ P and d H (u) ≤ 11, we have |N (u)| ≥ 1 and N (u) ≤ 11. In G let u ∈ N (u) be a two degree neighbour of u such that N (u ) = {u, u }. Now by minimality of G, the graph G \ uu admits an acyclic edge-colouring c using a set C of ∆ + 12 colours. Let F u = {c (ux)|x ∈ N (u)} and F u = {c (ux)|x ∈ N (u)}. Now if c(u u ) / ∈ F u we are done since |F u ∪ F u | ≤ ∆ and thus there are at least 12 candidate colours which are also valid by Lemma 2.4. We know that |F v | ≤ 11. If c (u u ) ∈ F v , then let c = c . Else if c (u u ) ∈ F v , then recolour edge u u using a colour from C \ (S u u ∪ F v ) to get an edge-colouring c (Note that |C \ (S u u ∪ F v )| ≥ ∆ + 12 -(∆ -1 + 11) = 2 and since u has degree one in G -{uu }, c is acyclic). Now if c(u u ) / ∈ F u the proof is already discussed. Thus c(u u ) ∈ F u .

Research partially supported by an ERC Advanced grant.

For all 1 ≤ i ≤ q colour v i w i with a colour not in F ∪ F i and distinct from the colours. This is possible since |F | + |F i | = ∆ -l -q + k -1 = ∆ -1.

We will now colour the edges uv i for 1 ≤ i ≤ q. Therefore let H 1 = ((A, B), E 1 ) be the bipartite graph with B the set of q + j colours {b 1 , . . . , b q+j } not in F and in which v i is adjacent to b j if c(v i w i ) = b j . As long as some v i has degree 0 then add an edge between a i and an isolated b j to obtain a bipartite graph H 2 = ((A, B), E 2 ). Then H 2 fulfils the hypothesis of Lemma 3.10 so there exists a perfect matching M of K A,B such that ((A, B), E 2 ∪ M ) has no cycle. For 1 ≤ i ≤ q, assign to each uv i the colour to which v i is linked in M .

In the same way as in the proof of Proposition 3.7, one shows that the obtained edge-colouring is acyclic.

3.2. Proof of Theorem 3.4. Lemma 3.11. Let > 0. There exists ∆ such that if ∆ ≥ ∆ then any ∆-minimal graph has average degree at least 4 -.

Proof. The result for = 1 2 implies the result for larger values of . Hence we assume that ≤ 1 2 . Let us assign an initial charge of

We perform the following discharging rules. Suppose that v is a 3-vertex. Then by Proposition 3.6 it has at least two (≥ 8)-neighbours. Hence it receives at least 2 × 1/2 by R1, R2 or R3 because

Then by Propositions 3.7 and 3.9, the most v can send is when it has three 2-neighbours with second neighbour of degree at most 3, one 2-neighbour with second neighbour of degree d for all 4 ≤ d ≤ d -1 and ∆ -d + 1 2-neighbours with second neighbour of degree at least d . Hence

Proof. [ of Theorem 3.4] If Theorem 3.4 were false, then a minimum counterexample G would be a ∆-minimum graph. So by Lemma 3.11, its average degree would be at least 4 -, a contradiction. Suppose that v is a 4-vertex. Then, since ∆ ≥ 18, by Proposition 3.6, it has either three (≤ 3)neighbours and one (≥ 10)-neighbour or at most two (≤ 3)-neighbours. In the first case, it sends 4/9 to each of its 3-neighbours and receives 2/3 form its (≥ 10)-neighbour. So f (v) ≥ 4 -3 × 4 9 + 2 3 = 10/3. In the second case, it sends 4/9 to at most 2 neighbours. So f (v) ≥ 4 -2 × 4 9 > 10/3. Suppose that v is a 5-vertex. Assume first that v has at most three (≤ 3)-neighbours. If it has at least one (3)-neighbour it sends at most 3/2 so f (v) ≥ 5 -3/2 > 10/3. If not it has three 2-neighbours. Let u 1 and u 2 be the two (≥ 4)-neighbours of v. By Proposition 3.6, d(u 1 ) + d(u 2 ) ≥ 11 since ∆ ≥ 16. Hence one of these two vertices is a (≥ 6)-vertex and it sends at least 4/9 to u. Hence f (v) ≥ 5 + 4/9 -7/4 > 10/3. Assume now that v has at least four (≤ 3)-neighbours. Let i be the number of 2-neighbours of v. Then by Proposition 3.6, v has exactly 4 -i 3-neighbours and its fifth neighbour has degree at least 6 + i since ∆ ≥ 17. Hence f (v) ≥ 5 -i. 7 12 -(4 -i) 1 3 + 1 -10 3(6+i) > 10/3. Suppose that d(v) = ∆ -l for 1 ≤ l ≤ 7. By Proposition 3.9, v is incident to at most ∆ -l -1 threads so its has at least one (≥ 3)-neighbour to which it sends at most 2/3. Moreover the most it can send is when it has exactly one 2-neighbour with second neighbour of degree d for each l + 2 ≤ d ≤ 9 and ∆ -9 2-neighbours with second neighbour of degree at least 10. Hence its final charge is Proof. [ of Theorem 3.2] If Theorem 3.2 would be false, a minimum counterexample G would be a ∆-minimum graph. So by Lemma 3.12, its average degree is at least 10/3, a contradiction.

4.

Acknowledgement. We would like to thank Jan van den Heuvel for helpful discussions.


Nathann Cohen
email: nathann.cohen@sophia.inria.fr

Frédéric Havet
email: fhavet]@sophia.inria.fr

Linear and 2-frugal choosability of graphs of small maximum average degree

A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L : V (G) → 2 N , there exists a 2-frugal (resp. linear)

In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.

Introduction

The notion of acyclic colouring was introduced by Grünbaum [START_REF] Grünbaum | Acyclic colourings of planar graphs[END_REF] in 1973 : a vertex colouring is acyclic if it is proper (no two adjacent vertices have the same colour), and if there is no bicoloured cycle (the subgraph induced by the union of any two colours classes is a forest). A colouring such that for every vertex v ∈ V (G), no colour appears more than p times in the neighborhood of v, is said to be p-frugal, a notion introduced by Hind, Molloy and Reed in [START_REF] Hind | Colouring a graph frugally[END_REF]. The p-frugal chromatic number of a graph G, denoted by Φ p (G), is the minimum number of colours in a p-frugal colouring of G and is clearly larger than ∆ p + 1. Hind, Molloy, and Reed [START_REF] Hind | Colouring a graph frugally[END_REF] proved that Φ p (G) ≤ max(p∆(G), e 3 p ∆(G) 1+1/p ). In addition, they show that this upper bound is tight up to within a constant factor by showing graphs G such that Φ p (G) ≥ 1 2p ∆(G) 1+1/p . Yuster [START_REF] Yuster | Linear colouring of graphs[END_REF] mixed the notions of 2-frugality and acyclicity, thus introducing the concept of linear colouring. A linear colouring of a graph is an acyclic and 2-frugal colouring. It can also be seen as a colouring such that the subgraph induced by the union of any two colour classes is a forest of paths (an acyclic graph with maximum degree at most two). The linear chromatic number of a graph G, denoted by Λ(G), is the minimum number of colours in a linear colouring of G. As a linear colouring is 2-frugal, Λ(G) ≥ Φ 2 (G) ≥ ∆ 2 + 1. Yuster proved in [START_REF] Yuster | Linear colouring of graphs[END_REF] that Λ(G) = O(∆(G) 3/2 ) in the general case, and he constructed graphs for which Λ(G) = Ω(∆(G) 3/2 ).

These concepts may be generalized to list colouring. Given a list assignment L : V (G) → 2 N , an Lcolouring of G is a colouring c such that c(v) ∈ L(v) for each vertex v. A graph G is p-frugally (resp. linearly) L-colourable if there is an L-colouring of G which is p-frugal (resp. linear). If G is p-frugally (resp. linearly) L-colourable for any assignment L verifying ∀v ∈ V (G), |L(v)| ≥ k, then G is said to be pfrugally k-choosable (resp. linearly k-choosable). The smallest integer k such that the graph G is p-frugally k-choosable is the p-frugal choosability or p-frugal list chromatic number of G and is denoted by Φ l p (G). The linear choosability or linear list chromatic number denoted Λ l (G) is defined analogously. The average degree of G is Ad

(G) = 1 |V (G)| ∑ v∈V (G) d(v) = 2|E(G)| |V (G)| . The maximum average degree of G is Mad(G) = max{Ad(H) | H is a subgraph of G}.
In [START_REF] Esperet | Linear choosability of graphs[END_REF], Esperet et al. proved some upper bounds on the linear choosability of graphs with small maximum average degree.

Theorem 1 (Esperet et al. [START_REF] Esperet | Linear choosability of graphs[END_REF]). Let G be a graph with maximum degree at most ∆:

1. If ∆ ≥ 3 and Mad(G) < 16 7 , then Λ l (G) = ∆ 2 + 1. 2. If Mad(G) < 5 2 , then Λ l (G) ≤ ∆ 2 + 2. 3. If Mad(G) < 8 3 , then Λ l (G) ≤ ∆ 2 + 3.
In this article, we show in Theorem. 2 that the above upper bounds on the maximum average degree may be assumed arbitrarily close to 3 when ∆ is large enough. When ∆ is small, we also improve some of the existing bounds (see Theorem. 3). After the submission of this paper, some results were again improved by Cranston and Yu [START_REF] Cranston | Linear choosability of sparse graphs[END_REF]. Since a linear colouring is 2-frugal, the results are also valid for 2-frugal choosability. However, since being 2-frugal is less restrictive than being linear, we improve some of them in this case (see Theorem. 4). All these results, added to those proved by Esperet et al. [START_REF] Esperet | Linear choosability of graphs[END_REF] which have not been improved, are summarized in the following table :

Mad(G) ∆ Λ l (G) < 16 7 ≈ 2.2857 ≥ 3 ≤ ∆ 2 + 1 Esperet et al. [2] < 39 16 = 2.4375 ≥ 5 ≤ ∆ 2 + 1 Theorem 3-1 < 48 19 ≈ 2.5263 ≥ 7 ≤ ∆ 2 + 1 Theorem 3-2 < 3 -3 ∆+1 ≥ 8 ≤ ∆ 2 + 1 Theorem 2-1 < 12 5 ≥ 3 ≤ ∆ 2 + 1 Cranston and Yu [1] < 5 2 ≤ ∆ 2 + 2 Esperet et al. [2] < 60 23 ≈ 2.6086 ≥ 5 ≤ ∆ 2 + 2 Theorem 3-3 < 3 -9 4∆+3 ≥ 7 ≤ ∆ 2 + 2 Theorem 2-2 < 3 ≥ 9 ≤ ∆ 2 + 2 Cranston and Yu [1] < 14 5 = 2.8 ≤ ∆ 2 + 3 Theorem 3-4 < 3 ≥ 12 ≤ ∆ 2 + 3 Theorem 2-3 < 3 ≤ ∆ 2 + 4 Theorem 3-5 Mad(G) Φ l 2 (G) ∆ < 5 2 ≤ ∆ 2 + 1 ≥ 7 Theorem 4-1 < 3 ≤ ∆ 2 + 3 Theorem 4-2
The girth g(G) of a graph G is the length of its smallest cycle or +∞ if G has no cycle. Euler's formula implies that a planar graph G has bounded maximum average degree in terms of its girth:

Mad(G) < 2 + 4 g(G) -2 . ( 1
)
This immediately gives to any result on graphs with bounded maximum average degree have an equivalent formulation for planar graphs with large girth. These are summarized in the following table together with those coming from the papers of Esperet et al. [START_REF] Esperet | Linear choosability of graphs[END_REF] and Raspaud and Wang [START_REF] Raspaud | Linear coloring of planar graphs with large girth[END_REF][START_REF] Raspaud | Linear colouring of planar graphs Research report 138406[END_REF] which are not improved here.

girth Λ l (G) ∆ ≥ 16 ≤ ∆ 2 + 1 ≥ 3 Esperet et al. [2] ≥ 7 ≤ ∆ 2 + 1 ≥ 13 Raspaud and Wang [6] ≥ 8 ≤ ∆ 2 + 1 ≥ 10 ≤ ∆ 2 + 2 Esperet et al ≥ 9 ≤ ∆ 2 + 2 ≥ 5 ≥ 7 ≤ ∆ 2 + 3 ≥ 5 ≤ ∆ 2 + 4 Cranston and Yu [1] ≤ 9∆ 10 + 5 ≥ 85 Raspaud and Wang [7] girth Φ l 2 (G) ∆ ≥ 6 ≤ ∆ 2 + 3
The proofs of our results are based on the same general idea. We study graphs which we call k-frugalminimal (resp. k-linear-minimal) -i.e. graphs that are not k-frugally colourable (resp. k-linear-colourable), while any of their proper subgraphs is. We first show in Section 2 that some configurations (i.e. subgraphs) may not appear in such a graph. We then use in Section 3 the discharging method to show that a graph containing none of these forbidden configurations must have larger average degree than assumed, giving a contradiction .

Forbidden configurations

Before establishing some lemmas, let us give some definitions. Let k be a non-negative integer. A k-vertex (resp. (≥ k)-vertex, (≤ k)-vertex) is a vertex of degree exactly k (resp. at least k, at most k). A k-neighbour of v is a k-vertex adjacent to v. (≥ k) and (≤ k)-neighbours are defined similarly. A k-thread in a graph G is an induced path (or cycle) of G with k + 1 edges, and so at least k internal vertices of degree 2.

Note that a k-frugal-minimal or k-linear-minimal graph is connected and in particular has no 0-vertex. We will sometimes use this easy fact without referring explicitly to it.

Linear colouring

Lemma 1. Let H be a k-linear-minimal or k-frugal-minimal graph. Proof. In the following, we only prove the assertions for linear colouring : 2-frugal colouring being less restrictive, all the proofs translate naturally. Suppose that one of the assertions of Lemma 1 does not hold.

1. If k ≥ ∆(H) 2 + 1, then H has no 1-vertex.
Let H be a k-linear-minimal graph for which it fails and L a k-list assignment such that H is not linearly L-colourable.

1. H contains a 1-vertex u. Let v be the neighbour of u. Let c be a linear L-colouring of Hu. We now extend c to u. The colour c(v) is forbidden. Moreover to preserve the 2-frugality at v, the colours appearing twice in the neighbourhood of v are also forbidden. There are at most ∆(H)-1 2 such colours. Hence, at most ∆(H) 2 colours in total are forbidden at u. Thus u can be coloured with a non-forbidden colour in its list L(u), and the colouring obtained is a linear L-colouring of H, which is a contradiction.

2 Let v be a 2-vertex of H with N(v) = {a, b} and deg(a) ≤ deg(b), such that deg(b) < 2(k -deg(a)) + 1.
Let c be a linear L-colouring of Hv.

- . Hence such an assignment is possible, and yields a k-linear L-colouring of H, a contradiction.

3. It follows directly from 2 which implies that if a 2-vertex has a 2-neighbour then its other neighbour has degree at least 3.

4. There is a configuration as depicted in Figure 1. with possibly x = u 1 , or x = u and w = u 1 .

u u u u u u d d d d u v w x u 1 u 2 Figure 1: Configuration of Case 4
By the minimality of H, there exists a linear L-colouring c of Hv. We now extend it to v :

-If c(u 1 ) = c(u 2 ), we colour v with c(v) ∈ L(v)\{c(u), c(w), c(u 1 )}.
There can be no bicoloured cycle, as c(v) is different from both c(u 1 ) and c(u 2 ), and the 2-frugality at u is preserved.

-If c(u 1 ) = c(u 2 ), we colour v with c(v) ∈ L(v)\{c(u), c(w), c(x)}.
There can be no bicoloured cycle, as c(v) is different from c(x), and c is 2-frugal.

5. There is a configuration as depicted in Figure 2. Possibly t i = u i and w i = u i for i = 1, 2, or some vertices in {w 1 , w 2 ,t 1 ,t 2 } are identified.

By the minimality of H there exists a linear L-colouring c of H -{u, v}. We now extend it to u and v : -If c(u 1 ) = c(u 2 ), we colour u with c(u) ∈ L(u)\{c(u 1 ), c(u 2 ), c(w)} and v with c(v) ∈ L(v)\{c(u), c(w), c(w 1 )}.

6. There is a configuration as depicted in Figure 3. Possibly t 3 = u = u 3 and u 1 = t 2 and t 1 = u 2 . In this case, a linear colouring of H -{u 1 , u 2 } can be extended into a linear colouring of H by assigning to u 1 a colour distinct from those of u and w 1 and to u 2 a colour distinct from those of u, u 1 and v 1 . This is a contradiction.

So we may assume that it is not the case. Then possibly some vertices of {t 3 , u 3 , v 3 , w 3 } may be identified.

u u u u u u u u u u u u u d d d d x t 1 w 1 u 1 v 1 t 2 w 2 u 2 v 2 t 3 w 3 u 3 v 3 Figure 3: Configuration of Case 6
By the minimality of H there exists a linear L-colouring c of H -{t 1 , u 1 , v 1 , w 1 , x}. We now extend it to t 1 , u 1 , v 1 , w 1 and x by sequentially colouring:

t 1 with c(t 1 ) ∈ L(t 1 )\{c(t 2 ), c(t 3 )}.

u 1 with c(u 1 ) ∈ L(u 1 )\{c(u 2 ), c(u 3 ), c(t 1 )}.

x with c(x) ∈ L(x)\{c(t 1 ), c(u 1 ), c(w 2 )}.

w 1 with c(w 1 ) ∈ L(w 1 )\{c(t 2 ), c(x)}.

v 1 with c(v 1 ) ∈ L(v 1 )\{c(v 2 ), c(x), c(w 1 )}.

There can be no bicoloured cycle through t 1 (resp. u 1 ) as its colour is different from c(t 3 ) (resp. c(u 3 )), and none going through w 2 as its colour is different from c(x).

7. There is a configuration as depicted in Figure 4. Possibly w 3 is one of {t, u, v} or w 3 = x and w 2 = t. In the later case, we get a contradiction as in Case 6, so we may assume that it does not occur. By the minimality of H there exists a linear L-colouring c of Hw 1 . We extend it to w 1 :

-If c(w 2 ) = c(x), then we colour w 1 with c(w 1 ) ∈ L(w 1 )\{c(x), c(w 3 ), c(v), c(t)}. There can be no bicoloured cycle as c(w 1 ) = c(w 3 ), and the 2-frugality at x is preserved.

-If c(w 2 ) = c(x), then we colour w 1 with c(w 1 ) ∈ L(w 1 )\{c(x), c(w 2 ), c(v), c(t)}. There can be no bicoloured cycle as c(w 2 ) = c(x), and the 2-frugality at x is preserved.

8. There is a configuration as depicted in Figure 5. Possibly, some of the vertices in {s 3 ,t 3 , u 3 , v 3 , w 3 } are the same or identified with x (by pairs). In the later case, without loss of generality, s 3 = x = t 3 , s 1 = t 2 and t 1 = s 2 . Then, by minimality of H, there exists a linear colouring c of H -{s 1 , s 2 }. It can be extended by colouring s 1 with a colour c(s 1 ) distinct from c(x) and the possible colour appearing twice on {u 1 , v 1 , w 1 }, and colouring s 2 with a colour c(s 2 ) distinct from c(x), c(s 1 ) and the possible colour appearing twice on {u 1 , v 1 , w 1 }. Hence we may assume that this case does not appear. By the minimality of H there exists a linear L-colouring c of H -{x, s 1 ,t 1 , u 1 , v 1 , w 1 }. We extend it to x, s 1 , t 1 , u 1 , v 1 , and w 1 by sequentially colouring:

w 2 w 3 s 1 s 2 s 3 v 1 v 2 v 3 u 1 u 2 u 3 t 1 t 2 t 3
s 1 with c(s 1 ) ∈ L(s 1 )\{c(s 2 ), c(s 3 )}.

t 1 with c(t 1 ) ∈ L(t 1 )\{c(t 2 ), c(t 3 ), c(s 1 )}.

u 1 with c(u 1 ) ∈ L(u 1 )\{c(u 2 ), c(u 3 ), c(s 1 ), c(t 1 )}.

v 1 with c(v 1 ) ∈ L(v 1 )\{c(v 2 ), c(u 1 ), c(t 1 ), c(s 1 )}.

x with c(x) ∈ L(x)\{c(s 1 ), c(t 1 ), c(u 1 ), c(v 1 )}.

w 1 with c(w 1 ) ∈ L(w)\{c(w 2 ), c(x), c(v 1 )}.

The 2-frugality at x is preserved as 4 different colours are assigned to the vertices s 1 , t 1 , u 1 and v 1 . Furthermore, there can be no bicoloured cycles going through s 1 and s 3 , t 1 and t 3 , u 1 and u 3 or w 1 and v 1 . Thus the obtained L-colouring is linear, a contradiction. 9. There is a configuration as depicted in Figure 6. Possibly, some of the vertices of {v 1 , v 2 , w 1 , w 2 } are identified or v 1 = w and w 1 = v. By the minimality of H, there exists a linear L-colouring c of Hu. We extend it to u :

We shall prove that after the discharging phase every vertex v has final charge w * (v) at least 3ε for some ε ≥ 0 to be determined. This implies that

Ad(H) = ∑ v∈V (H) w(v) |V (H)| = ∑ v∈V (H) w * (v) |V (H)| ≥ 3 -ε which contradicts Mad(G) < 3 -ε.
By Lemma 1-1, there is no (≤ 1)-vertex. For any d ≥ 3, every d-vertex send at least d times α d , so its final charge is at least

d -d • α d = 3 -ε.
Let us now examine the final charge of 2-vertices. We set d q = 2( ∆ 2 + qd) + 1. By Lemma 1-2, every 2-vertex having a d-neighbour has also a (≥ d q )-neighbour. Observe that d q > ∆ if d ≤ q, thus no 2-vertex has a (≤ q)-neighbour.

If q ≥ 2, then a 2-vertex v has no 2-neighbour. Hence by Lemma 1-2, it has a d 1 -neighbour and a d 2neighbour, with 2

< d = d 1 ≤ d q ≤ d 2 . Since α 3 ≤ α 4 ≤ • • • ≤ α ∆ , the final charge of v is at least w * (v) = 2 + α d 1 + α d 2 ≥ 2 + α d + α d q .
If q = 1 a 2-vertex has either no 2-neighbour and as above its final charge is at least 2 + α d + α d q or it has a 2-neighbour and, by Lemma 1-2, its other neighbour is a ∆-vertex, so it final charge is at least 2 + α ∆ .

Hence, to prove Theorem 2, it is sufficient to show that 2 + α d + α d q ≥ 3ε, for all d ≤ d q and also 2 + α ∆ ≥ 3ε when q = 1.

2 + α d + α d q ≥ 3 -ε is equivalent to P(d) ≥ 0 with P(d) = (1 + ε)dd q + (ε -3)(d + d q ). Since d q = 2( ∆ 2 + q -d) + 1, P(d) is a polynomial of degree 2 in d of the form -2(1 -ε)d 2 + A • d + B
for some constant A and B (note that the coefficient of d 2 is negative). Hence to verify that P(d) ≥ 0 for all possible values of d it suffices to prove it for the smallest and largest d such that d ≤ d q , namely max(3, q + 1) and ∆+2q+2 3 (it actually is ∆+2q+2

3 if ∆ is odd and ∆+2q+1 3 if ∆ is even). If q ≥ 2
, we obtain the following two conditions:

ε ≥ 3(q + 1) -(q -2)∆ q + 1 + (q + 2)∆ ε ≥ 16 -2q -∆ 8 + 2q + ∆
For q = 3 and ∆ ≥ 12 the right hand sides of these two inequalities are negative. So they are satisfied for ε = 0, which proves Theorem 2-3. For q = 2 and ∆ ≥ 7 then 9 3+4∆ ≥ 12-∆ 12+∆ and so the above inequalities are satisfied for ε = 9 3+4∆ . This proves Theorem 2-2. If q = 1, we have the three following conditions, the first two given by P(d) and the third one by 2

+ α ∆ ≥ 3 -ε. ε ≥ 9 4∆ -5 ε ≥ 14 -∆ 10 + ∆ ε ≥ 3 ∆ + 1
But 3 ∆+1 ≥ 9 4∆-5 and 3 ∆+1 ≥ 14-∆ 10+∆ when ∆ ≥ 8. So the above inequalities are satisfied for ε = 3 ∆+1 . This proves Theorem 2-1.

Graphs of small maximum degree

In this subsection we prove the following theorem.

Theorem 3. Let G be a graph with maximum degree at most ∆:

1. If ∆ ≥ 5 and Mad(G) < 39 16 , then Λ l (G) ≤ ∆ 2 + 1. 2. If ∆ ≥ 7 and Mad(G) < 48 19 , then Λ l (G) ≤ ∆ 2 + 1. 3. If ∆ ≥ 5 and Mad(G) < 60 23 , then Λ l (G) ≤ ∆ 2 + 2. 4. If Mad(G) < 14 5 , then Λ l (G) ≤ ∆ 2 + 3. 5. If Mad(G) < 3. Then Λ l (G) ≤ ∆ 2 + 4. Proof.
The proofs of all statements are similar: we assume the existence of a counter-example G such that Mad(G) < M (we first consider M as a variable), from which we deduce the existence of a subgraph H which is k-linear-minimal. We then use the discharging method to reach a contradiction.

We give to each vertex v of H an initial charge w(v) equal to its degree deg H (v) in H. The average charge is then equal to the average degree of H which is at most Mad(G). Then, we define discharging rules by which vertices will exchange some of their charge, keeping the average constant. We then want to prove with the help of the lemmas of the previous section that each vertex v has a final charge w * (v) at least M and so strictly greater than the average charge, which is a contradiction.

Of course, we want to find rules such that M is as large as possible in each case : for this reason, the following proofs actually define the constraints of a Linear Programme in which M is the objective value, and whose variables are the charges exchanged by the vertices during the discharging phase. At the end of each proof, we give an optimal solution of the given Linear Programme which proves the results.

1. Let G be a graph with maximum degree

∆ ≥ 5 such that Mad(G) < M. Set k 1 = ∆ 2 + 1. Suppose by way of contradiction that Λ l (G) > k 1 . Then G has a subgraph H which is k 1 -linear-minimal.
Let us assign to every vertex of H an initial charge

w(v) = deg H (v). Then ∑ v∈V (H) w(v) = ∑ v∈V (H) d(v) = Ad(H) • |V (H)|.
We now apply the following discharging rules. At the end we want that the final charge of every vertex is at least M. This implies

Ad(H) = ∑ v∈V (H) w(v) |V (H)| = ∑ v∈V (H) w * (v) |V (H)| ≥ M which contradicts Mad(G) < M.
We now define constraints on M and the α i and α i guaranteeing the the final charge w * (v) of every vertex v of H is at least M.

As there are no (≤ 1)-vertices by Lemma 1-1, let us examine the final charge w * (v) of a (≥ 2)-vertex v.

• If v is a 2-vertex then by Lemma 1-3 and 1-4 it has either two 3-neighbours, or one 3-neighbour and one (≥ 4)-neighbour, or one 2-neighbour and one (≥ 4)-neighbour. In the first case w * (v) = 2 + 2α 3 , on the second w * (v) ≤ 2 + α 3 + α 4 and in the last one w * (v) = 2 + α 4 . So the required constraints are

M ≤ 2 + 2α 3 and M ≤ 2 + α 3 + α 4 and M ≤ 2 + α 4 .
• If v is a 3-vertex adjacent to three 2-neighbours, none of them can be adjacent to another 3-vertex by Lemma 1-5, and so will give at most 3α 3 . If it is adjacent to two 2-neighbours then it gives at most max{2α 3 , 2α 3 }. Hence, we obtain the constraints M ≤ 3 -3α 3 and M ≤ 3 -2α 3 .

• If v is a 4-vertex, by Lemma 1-6 it can not be adjacent to four 2-threads. Then it gives at most 3α 4 + α 4 .

(Here we assume implicitly that α 4 ≤ α 4 which is intuitively true but a priori not proved. However this inequality is satisfied by the solution giving the optimal value of M and so our assumption is a posteriori correct). Thus we obtain the constraint M ≤ 4 -3α 4α 4 .

• If v is a k-vertex with k ≥ 5, it will give at most give kα 4 yielding the constraints M ≤ kkα 4 .

The optimal value M = 39 16 is obtained for α 3 = 7 32 , α 3 = 3 16 , α 4 = 7 16 and α 4 = 1 4 .

2. Let G be a graph with maximum degree ∆ ≥ 7 such that Mad(G) < M. Set k 1 = ∆ 2 + 1. Suppose by way of contradiction that Λ l (G) > k 1 . Then G has a subgraph H which is k 1 -linear-minimal.

Let us assign to every vertex of H an initial charge w(v) = deg H (v) and apply the following discharging rules.

Rule 1. A 3-vertex sends α 3 to each of its 2-neighbours. Rule 2. A (≥ 4)-vertex sends α 4 to its 2-neighbours which are in a 2-thread and α 4 to its other 2neighbours.

Let us now define constraints to ensure that the final charge w * (v) of every vertex v of H is at least M, a contradiction. Again there are no (≤ 1)-vertices by Lemma 1-1.

• Suppose that v is a 2-vertex. Then by Lemma • If v is a 3-vertex it sends at most α 3 to each neighbour. This yields the constraints M ≤ 3 -3α 3 .

• If v is a 4-vertex then by Lemma 1-7, it is incident to no 2-thread, yielding M ≤ 4 -4α 4 .

• If v is a 5-vertex then by Lemma 1-8, it is incident to at most four 2-threads, yielding M ≤ 5 -4α 4α 4 (again we implicitly assume α 4 ≥ α 4 which is satisfied by the solution giving the optimal value).

• If v is a k-vertex with k ≥ 6, it sends at most α 4 to each neighbour. Thus M ≤ kkα 4 .

The optimal value M = 48 19 is obtained for α 3 = 3 19 , α 4 = 10 19 and α 4 = 7 19 .

3. Let G be a graph with maximum degree ∆ ≥ 5 such that Mad(G) < M. Set k 2 = ∆ 2 + 2. Suppose by way of contradiction that Λ l (G) > k 2 . Then G has a subgraph H which is k 2 -linear-minimal.

We assign to every vertex of H an initial charge w(v) = deg H (v) and apply the following discharging rules.

Rule 1. A 3-vertex sends α 3 to each of its 2-neighbours Rule 2. A (≥ 4)-vertex sends α 4 to each of its 2-neighbours having no (≤ 3)-neighbour.

Rule 3. A (≥ 4)-vertex sends α 4 to each of its 2-neighbours having a 3-neighbour.

Let us now define constraints to ensure that the final charge w * (v) of every vertex v of H is at least M, which is a contradiction.

• If v is a 2-vertex then it has no 2-neighbour by Lemma 1-11. If it has a 3-neighbour its other neighbour is a (≥ 4)-neighbour according to Lemma 1-9. yielding M ≤ 2 + α 3 + α 4 . If v has no 3-neighbour, then we get M ≤ 2 + 2α 4 .

• If v is a 3-vertex it sends at most 3α 3 , yielding M ≤ 3 -3α 3 .

• If v is a 4-vertex then by Lemma 1-10, it has at most one 2-neighbour that has a 3-neighbour, yielding M ≤ 4α 4 -3α 4 (with the assumption α 4 ≥ α 4 ).

• If v is a k-vertex with k ≥ 5, it sends at most kα 4 , yielding M ≤ kkα 4 .

The optimal value M = 60 23 is obtained for α 3 = 3 23 , α 4 = 7 23 and α 4 = 11 23 .

4. Let G be a graph such that Mad(G) < M. Set k 3 = ∆ 2 + 3. Suppose by way of contradiction that Λ l (G) > k 3 . Then ∆ ≥ 3, as every graph with maximum degree at most 2 is linearly 3-choosable. Moreover G has a subgraph H which is k 3 -linear-minimal.

Let us assign to every vertex of H an initial charge w(v) = d H (v) and apply the following discharging rule.

Rule 1. A (≥ 4)-vertex sends α 4 to each of its 2-neighbours

Let us now define constraints to ensure that the final charge w * (v) of every vertex v of H is at least M, which is a contradiction.

• If v is a 2-vertex then it has no (≤ 3)-neighbour by Lemmas 1-11 and 1-12. This gives M ≤ 2 + 2α 4 .

• If v is a 3-vertex then its charge does not change, yielding M ≤ 3.

• If v is a 4-vertex then by Lemma 1-13, it has at most three 2-neighbours. This yields M ≤ 4 -3α 4 .

• If v is a k-vertex with k ≥ 5, it sends at most α 4 to each neighbour, yielding M ≤ kkα 4 .

The optimal value M = 14 5 is obtained for α 4 = 2 5 .

5. Let G be a graph such that Mad(G) < M. Set k 4 = ∆ 2 + 4. Suppose by way of contradiction that Λ l (G) > k 4 . Then ∆ ≥ 3, as every graph with maximum degree at most 2 is linearly 3-choosable. Moreover G has a subgraph H which is k 4 -linear-minimal.

Let us assign to every vertex of H an initial charge w(v) = deg H (v) and apply the following discharging rule.

Rule 1. A (≥ 4)-vertex sends α 4 to each of its 2-neighbours.

Let us now define constraints to ensure that the final charge w * (v) of every vertex v of H is at least M, which is a contradiction.

• If v is a 2-vertex then it has no (≤ 3)-neighbour by Lemmas 1-11 and 1-12. This gives M ≤ 2 + 2α 4 .

• If v is a 3-vertex, its charge is unchanged. This gives M ≤ 3.

• If v is a 4-vertex then by Lemma 1-14, it has at most two 2-neighbours, yielding M ≤ 4 -2α 4 .

• If v is a 5-vertex then by Lemma 1-15, it has at most four 2-neighbours. This gives M ≤ 5 -4α 4 .

• If v is a k-vertex with k ≥ 6, it sends at most kα 4 . Thus M ≤ kkα 4 .

The optimal value M = 3 is obtained for α 4 = 1 2 .

2-frugal colouring

In this subsection we prove the following theorem.

2 .

 2 For every 2-vertex v with N(v) = {a, b} and deg(a) ≤ deg(b), we have deg(b) ≥ 2(kdeg(a)) + 1.

3 . 6 . 7 . 2 + 3 , 2 + 3 , 2 + 4 , 2 + 4 ,

 36723232424 If k ≥ 3, then H contains no 3-thread. 4. If k ≥ 4, then no 3-vertex is incident to a 2-thread. 5. Assume k ≥ 4. If a 3-vertex has three 2-neighbours, then the second neighbour of each of those is a (≥ 4)-vertex. If k ≥ 4, then no 4-vertex is adjacent to four 2-threads. If k ≥ 5, then no 4-vertex is incident to a 2-thread. 8. If k ≥ 5, then no 5-vertex is incident to five 2-threads. 9. If k ≥ 5, then a 2-vertex has at most one 3-neighbour.10. If k ≥ 5, then a 4-vertex is not adjacent to two 2-vertices having each a 3-neighbour.11. If k ≥ ∆(H)12. If k ≥ ∆(H) there are no adjacent 3-vertex and 2-vertex.13. If k ≥ ∆(H) then every 4-vertex has at most three 2-neighbours.14. If k ≥ ∆(H) then every 4-vertex has at most two 2-neighbours.15. If k ≥ max 6, ∆(H) then every 5-vertex has at most four 2-neighbours.

2 < 2 + 2 < 2 +

 2222 If c(a) = c(b), let us assign to v a colour c(v) ∈ L(v) different from the ones of the other neighbours of a (i.e. there are at most deg(a) -1 of them), c(a), and every colour which is repeated at least twice in the neighbourhood of b (i.e. there at most deg(b)-1 kdeg(a) of them). Doing so, we obtain a k-linear L-colouring of H, a contradiction. -If c(a) = c(b), let us assign to v a colour c(v) ∈ L(v) different from c(a), c(b), and every colour which is repeated at least twice in the neighbourhood of a or in the neighbourhood of b. The number of forbidden colours is at most 2 + deg(a)-1 deg(b)-1 deg(a) -2 + kdeg(a) = k because deg(a) ≥ 2 and so deg(a) ≥ 2 + deg(a)-1 2

1 Figure 2 :-

 12 Figure 2: Configuration of Case 5

Figure 4 :

 4 Figure 4: Configuration of Case 7

Figure 5 :

 5 Figure 5: Configuration of Case 8

2 Figure 6 :

 26 Figure 6: Configuration of Case 9

Rule 1 .

 1 A 2-vertex having two 3-neighbours receives α 3 from each of them. Rule 2. A 2-vertex having only one 3-neighbour receives α 3 from it. Rule 3. A 2-vertex having a 2-neighbour and a (≥ 4)-neighbour receives α 4 from it. Rule 4. A 2-vertex having a (≥ 3)-neighbour and a (≥ 4)-neighbour receives α 4 from its (≥ 4)neighbour.

Theorem 4 .

 4 Let G be a graph with maximum degree (at most) ∆1. If ∆ ≥ 7 and Mad(G) < 5 2 , then Φ l 2 (G) ≤ ∆ 2 + 1.

2 . 3 .

 23 If Mad(G) < 3, then Φ l 2 (G) ≤ ∆ 2 + Proof. 1. Let G be a graph with maximum degree ∆ ≥ 7 such that Mad(G) < M. Set k 1 = ∆ 2 + 1 ≥ 5. Suppose by way of contradiction that Φ l 2 (G) > k 1 . Then G has a subgraph H which is k 1 -frugal-minimal. Let us assign to every vertex of H an initial charge w(v) = d H (v). Then ∑ v∈V (H) w(v) = ∑ v∈V (H) d(v) = Ad(H) • |V (H)|.Let us call a 2-vertex bad if it has a 2-neighbour, and good otherwise. We now apply the following discharging rules.

  1-3 it has at most one 2-neighbour. If v has one 2neighbour then, by Lemma 1-4, it has a (≥ 4)-neighbour from which it receives α 4 . We obtain the constraint M ≤ 2 + α 4 . If v has no 2-neighbour then, by Lemma 1-9, it has a (≥ 4)-neighbour from which it receives α 4 . Its other neighbour is a (≥ 3)-neighbour from which it receives α 3 . Hence we get M ≤ 2 + α 4 + α 3 .

-If c(v) = c(w), we colour u with c(u) ∈ L(u)\{c(v), c(v 1 ), c(v 2 ), c(w 1 )} to prevent the formation of a bicoloured cycle and preserve the 2-frugality at v and w.

-If c(v) = c(w), we colour u with c(u) ∈ L(u)\{c(v), c(v 1 ), c(w 1 ), c(w)} to preserve the 2-frugality at v and w. There can be no bicoloured cycles because c(v) = c(w).

Hence H is linearly L-colourable, a contradiction.

10. There is a configuration as depicted in Figure 7. Possibly some vertices of {v 1 , v 1 , v 2 , v 2 , v 3 , v 4 } are the same, or, for i ∈ {1, 2}, v i = u and v i = v i+2 . By the minimality of H there exists a linear L-colouring c of H -{v 1 , v 2 }. We extend it to v 1 and v 2 :

-If c(v 1 ) = c(u), we colour v 1 with c(v 1 ) ∈ L(v 1 )\{c(u), c(v 1 ), c(v 1 ), c(v 4 )}. There can be no bicoloured cycle through v 1 as it is different from both v 1 and v 1 , and the 2-frugality at v 1 is preserved.

There can be no bicoloured cycle through v 1 as c(v 1 ) = c(u), and the 2-frugality at v 1 is preserved.

We colour v 2 with symmetrical rules, replacing v 4 by v 3 .

As c(v 4 ) = c(v 1 ) and c(v 3 ) = c(v 2 ), the 2-frugality of c is preserved.

11. It follows from 2. Indeed if a 2-vertex would have a 2-neighbour then its second neighbour has degree at least ∆(H) + 1, a contradiction.

12. There is a configuration as depicted in Figure 8 with possibly -

) that is different from c(u), the colours appearing twice in the neighbourhood of v 1 (in order to preserve the 2-frugality at this vertex) and different from c(v 2 ) and c(v 3 ) to prevent the apparition of bicoloured cycles.

-If c(u) = c(v 1 ), we colour v 1 with c(v 1 ) ∈ L(v 1 ) that is different from c(u) and c(v 1 ), the colours appearing twice in the neighbourhood of v 1 (in order to preserve 2-frugality at this vertex) and different from c(v 2 ) to preserve the 2-frugality at u. There can be no bicoloured cycles as c(u) = c(v 1 ).

In both cases, H is linearly L-colourable, a contradiction.

Figure 9: Configuration of Case 13

13. There is a configuration as depicted in Figure 9 with possibly some of the vertices in

By the minimality of H there exists a linear L-colouring c of H -{u, v 1 , v 2 , v 3 , v 4 }. We extend it to u, v 1 , v 2 , v 3 and v 4 by sequentially colouring:

u with c(u) ∈ L(u) \ {c(v 1 ), c(v 2 ), c(v 3 ), c(v 4 )} to prevent the apparition of bicoloured cycles.

v 1 with c(v 1 ) ∈ L(v 1 ) different from c(u), c(v 1 ) and the colours appearing twice in the neighbourhood of v 1 .

-

and the colours appearing twice in the neighbourhood of v 2 .

-

and the colours appearing twice in the neighbourhood of v 3 .

v 4 with c(v 4 ) ∈ L(v 4 ) different from c(u), c(v 4 ), c(v 1 ) and the colours appearing twice in the neighbourhood of v 4 .

There can be no bicoloured cycle with this colouring of H and c is 2-frugal because 3 vertices among {v 1 , v 2 , v 3 , v 4 } cannot share the same colour. Then H is linearly L-colourable, a contradiction.

14. There is a configuration as depicted in Figure 10 with possibly some of the vertices in By the minimality of H there exists a linear L-colouring c of H -{u, v 1 , v 2 , v 3 }. We extend it to u, v 1 , v 2 and v 3 by sequentially colouring:

) (to avoid any bicoloured cycle) and the colours appearing twice in the neighbourhood of v 4 .

-

, and the colours appearing twice in the neighbourhood of v 1 .

-

, and the colours appearing twice in the neighbourhood of v 3 .

-

, and the colours appearing twice in the neighbourhood of v 2 .

There is no bicoloured cycle containing u because c(u) is different from c(v 1 ), c(v 2 ) and c(v 3 ). Moreover, the 2-frugality at u is assured, as 3 vertices among {v 1 , v 2 , v 3 , v 4 } cannot share the same colour. Hence H is linearly L-colourable, a contradiction.

15. There is a configuration as depicted in Figure 11 with possibly some of the vertices in v 1 with c(v 1 ) ∈ L(v 1 ) different from c(v 1 ), and the colours appearing twice in the neighbourhood of v 1 .

-

, and the colours appearing twice in the neighbourhood of v 2 .

v 3 with c(v 3 ) ∈ L(v 3 ) different from c(v 3 ), c(v 1 ), c(v 2 ), and the colours appearing twice in the neighbourhood of v 3 .

-

) and the colours appearing twice in the neighbourhood of v 5 .

u with c(u) ∈ L(u) different from c(v 1 ), c(v 2 ), c(v 3 ), c(v 5 ), and c(v 4 ).

v 4 with c(v 4 ) ∈ L(v 4 ) different from c(v 4 ), c(u), and the colours appearing twice in the neighbourhood of v 4 .

There is no bicoloured cycle using v 4 because c(v 4 ) = c(u). Moreover there is no bicoloured cycle using both v i and v j , for i < j and i, j ∈ {1, 2, 3, 5} as c(v 1 ), c(v 2 ), c(v 3 ) and c(v 5 ) are all distionct. For the same reason, the 2-frugality at u is assured. Thus H is linearly L-colourable, a contradiction.

2-frugal colouring

Lemma 2. Let H be a k-frugal-minimal graph.

(i) If k ≥ 4, then no 4-vertex is incident to two 2-threads.

(ii) If k ≥ ∆ 2 + 3, then a 4-vertex has at most one 2-neighbour.

(iii) If k ≥ max 6, ∆ 2 + 3 , then a 5-vertex has at most four 2-neighbour.

Proof. Suppose that one of the assertions of Lemma 2 does not hold. Let H be a k-frugal-minimal graph for which it fails and L a k-list assignment such that H is not 2-frugally L-colourable.

(i) There is a configuration as depicted in Figure 12.

Figure 12: Configuration of Case (ii)

By the minimality of H there exists a 2-frugal L-colouring c of H -{v 1 , v 2 }. We extend it to v 1 and v 2 by sequentially colouring:

(ii) There is a configuration as depicted in Figure 13 with possibly some of the vertices in

By the minimality of H there exists a 2-frugal L-colouring c of H -{v 1 , v 2 }. We extend it to v 1 and v 2 by sequentially colouring:

) and the colours appearing twice in the neighbourhood of v 1 .

-

and the colours appearing twice in the neighbourhood of v 2 .

c is 2-frugal, given that c(v 1 ) = c(v 4 ) and c(v 2 ) = c(v 3 ). Hence, H is 2-frugally L-colourable, a contradiction.

(iii) There is a configuration as depicted in Figure 14 with possibly some vertices in

By the minimality of H there exists a 2-frugal L-colouring c of H -{u, v 1 , v 2 , v 3 , v 4 , v 5 }. We extend it to u, v 1 , v 2 , v 3 , v 4 and v 5 by sequentially colouring:

, and the colours appearing twice in the neighbourhood of v 1 .

-

) and the colours appearing twice in the neighbourhood of v 2 .

-

and the colours appearing twice in the neighbourhood of v 3 .

-

and the colours appearing twice in the neighbourhood of v 4 .

-

) and the colours appearing twice in the neighbourhood of v 5 .

-

The colouring is 2-frugal at u because no three vertices of {v 1 , v 2 , v 3 , v 4 , v 5 } can share the same colour as there is no stable set of size 3 in the auxiliary graph depicted on the right of Figure 14. Thus H is 2-frugally L-colourable, a contradiction.

3 Main results

Linear colouring -asymptotic result

In this subsection, we prove the following theorem:

Theorem 2. Let G be a graph of maximum degree at most ∆.

3. If Mad(G) < 3 and ∆ ≥ 12 then Λ l (G) ≤ ∆ 2 + 3. Proof. The proof of the three statements are similar.

We assume the existence of a counter-example G with maximum degree at most ∆ such that Mad(G) < 3-ε (we first consider ε as a variable). G then contains a subgraph H which is ( ∆ 2 + q)-linear-minimal with q = 1, 2 and 3 depending on the statement. We give to each vertex v of H an initial charge w(v) equal to its degree deg H (v) in H. The average charge is then equal to the average degree of H which is at most Mad(G).

We then use the following discharging rule :

to its 2-neighbours. 2. Let G be a graph such that Mad(G) < M. Set k 3 = ∆ 2 + 3. Suppose by way of contradiction that Φ l 2 (G) > k 3 . Then G has a subgraph H which is k 1 -frugal-minimal. We assign to every vertex of H an initial charge w(v) = deg H (v) and apply the following discharging rule.

Rule 1. ≥ 4-vertices give α 4 to each of their 2-neighbours.

Let us now define constraints to ensure that the final charge w * (v) of every vertex v of H is at least M, which is a contradiction.

• There are no 1-vertices by Lemma 1-1.

• If v is a 2-vertex, by Lemma 1-11 it does not have 2-neighbours, and by Lemma 1-12 it can not have any 3-neighbour either. Hence M ≤ 2 + 2α 4 .

• If v is a 3-vertex, M ≤ w * (v) = 3.

• If v is a 4-vertex, by Lemma 2-ii it has at most one 2-neighbour, yielding M ≤ 4α 4 .

• If v is a 5-vertex, by Lemma 2-iii it has at most four 2-neighbours, giving M ≤ 5 -4α 4 .

• If v is a k-vertex with k ≥ 6, then it sends at most α 4 to each of its neighbours. This yields M ≤ 6 -6α 4 .

The optimal value M = 3 is obtained for α 4 = 1 2 .


Nicole Eggemann

Frédéric Havet

Steve Noble

k-L(2, 1)-labelling for planar graphs is NP-complete for k ≥ 4

k-L(2,1)-Labelling for Planar Graphs is NP-Complete

for k ≥ 4.

The Frequency Assignment Problem asks for assigning frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference. One of the graph theoretical models of this problem which is well elaborated is the notion of distance constrained labelling of graphs. An L(2, 1)-labelling of a graph G is a mapping from the vertex set of G into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used. In this model, the vertices of G represent the transmitters and the edges of G express which pairs of transmitters are too close to each other so that an undesired interference may occur, even if the frequencies assigned to them differ by 1. This model was introduced by Roberts [START_REF] Roberts | Private communication to J. Griggs[END_REF] and since then the concept has been intensively studied (See the survey of Yeh [START_REF] Yeh | A survey on labeling graphs with a condition at distance two[END_REF]).

In their seminal paper, Griggs and Yeh [START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF] proved that determining the minimum span of a graph G, denoted λ 2,1 (G), is an NP-hard problem. Fiala et al. [START_REF] Fiala | Fixed-parameter complexity of λ-labelings[END_REF] proved that deciding λ 2,1 (G) ≤ k is NPcomplete for every fixed k ≥ 4 and later Havet and Thomassé [START_REF] Havet | Complexity of (p, 1)-total labelling[END_REF] proved that for any k ≥ 4, it remains NP-complete when restricted to bipartite graphs (and even a restricted family of bipartite graphs, i.e incidence graphs or first division of graphs). When the span k is part of the input, the problem is nontrivial for trees but a polynomial time algorithm based on bipartite matching was presented in [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF]. Moreover, somewhat surprisingly, the problem becomes NP-complete for series-parallel graphs [START_REF] Fiala | Distance Constrained Labelings of Graphs of Bounded Treewidth[END_REF], and thus the L(2, 1)-labelling problem belongs to a handful of problems known to separate graphs of tree-width 1 and 2 by P/NP-completeness dichotomy. Regarding planar graphs, Bodlaender et al. [START_REF] Bodlaender | Approximations for lambda-Colorings of Graphs[END_REF] showed that deciding if the span of a planar graph is at most k is NP-complete for any fixed k ≥ 8. In this paper, we show that it is also NP-complete for 4 ≤ k ≤ 7.

Preliminaries

Proposition 1 Let G be a graph admitting a k-L(2, 1)-labelling. Then the following hold:

(i) G has no vertex of degree at least k.

(ii) every vertex of degree k -1 is labelled 0 or k.

2 λ 2,1 (G) ≤ 5 Theorem 2
The following theorem is NP-complete:

Instance: A graph G. Question: λ 2,1 (G) ≤ 5?
Proof. We give a reduction to BW-colouring.

Let G be a cubic graph. Let H(G) be the graph obtained from G by doing the following.

• For every vertex v ∈ V (G), we add a vertex w v adjacent to it; and

• we replace every edge uv by the gadget graph G uv depicted in Figure 1.

b u v u a v a u b v c d e 1 e 2 f g 1 g 2 e 3
Figure 1: The edge gadget G uv

We will now show that G has a BW-colouring if and only if H(G) has an L(2, 1)-labelling of span 5.

Suppose first that H(G) has an L(2, 1)-labelling L of span 5. Then by Proposition 1-(ii), every vertex of V (G) is labelled 0 or 5 because it has degree 4 in H(G). Let B (resp. W ) be the set of vertices v of G such that L(v) = 0 (resp. 5). We shall prove that in G every v ∈ B has exactly two neighbours in B and every vertex in W has exactly two neighbours in W . The sets B and W will then be the colour classes of the desired colouring.

In order to prove this, we need the following lemma.

Lemma 3 (i) If L(u) = L(v) = 0 then (L(a u ), L(a v )) ∈ {(2,
(v) + d -(v) ≥ 2. So d + (v) ≥ 1. For ∑ v∈B d + (v) = ∑ v∈B d -(v), it follows that d + (v) = d -(v) =
(a u ) = 5, L(a v ) = 1, L(b u ) = 2, L(b v ) = 3, L(c) = 0, L(d) = 5, L(e 1 ) = 2, L(e 2 ) = 3, L(e 3 ) = 1, L( f ) = 0, L(g 1 ) =

  [START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF],[START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF][START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF],[START_REF] Fiala | Distance Constrained Labelings of Graphs of Bounded Treewidth[END_REF][START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF], (5, 3)}.(ii) If L(u) = 0 and L(v) = 5 then (L(a u ), L(a v )) = (4, 1).Proof. (i) By definition of L(2, 1)-labelling, L(a u ) and L(a v ) are both in {2, 3, 4, 5}. As |L(a u ) -L(a v )| ≥ 2 then (L(a u ), L(a v )) ∈ {(2, 4), (4, 2), (2, 5), (5, 2), (3, 5)(5, 3)}. Suppose for a contradiction that (L(a u ), L(a v )) ∈ {(2, 4), (4, 2)}. By symmetry, we may assume that (L(a u ), L(a v )) = (2, 4). Then L(b u ) = 5 and L(b v ) = 1. The vertices d and f have degree four and thus, by Proposition 1-(ii), are labelled in {0, 5} and since dist(d, f ) = 2, {L(d), L( f )} = {0, 5}. This implies that {L(e 1 ), L(e 2 )} = {2, 3}. But then the vertex c cannot be labelled, a contradiction. (ii) By definition of L(2, 1)-labelling, L(a u ) ∈ {2, 3, 4} and L(a v ) ∈ {0, 1, 2}. As |L(a u ) -L(a v )| ≥ 2 then (L(a u ), L(a v )) ∈ {(4, 1), (4, 2), (3, 1)}. Suppose for a contradiction that (L(a u ), L(a v )) = (4, 1). By the label symmetry x → 5x, we may assume that (L(a u ), L(a v )) = (4, 2). Hence L(b u ) = 1 and L(b v ) = 0. Now the vertices d and f have degree four and thus, by Proposition 1-(ii), are labelled in {0, 5}. As dist(b v , d) = 2, L(d) = 5 and as dist(d, f ) = 2, L( f ) = 0. Now {L(e 1 ), L(e 2 )} = {2, 3}. But then the vertex c cannot be labelled, a contradiction. By Lemma 3 (i), for any edge uv ∈ G[B], we have L(a u ) = 5 or L(a v ) = 5. Let us orient uv from u to v if L(a v ) = 5 and from v to u otherwise. We call D the obtained digraph. Let v ∈ B. It has at most one neighbour labelled 5, for every v ∈ B, d -(v) ≤ 1. In addition, it has at most one neighbour labelled 4 and thus by Lemma 3-(ii), d +

  1 for every vertex v ∈ B. Hence every v ∈ B has exactly two neighbours in B. Analogously, every vertex in W = {v ∈ V (G) | L(v) = 5} has exactly two neighbours in W . The sets B and W form the colour classes of the desired colouring. Suppose now that G has a BW-colouring. Let us now show an L(2, 1)-labelling L of H(G). The graphs G[B] and G[W ] are union of cycles. Orienting each cycle directly we obtain digraphs D[B] and D[W ] in which every vertex has indgree and outdegree one. Let us now define the labelling defined. We first label the vertices of G and the w v . If v ∈ B then L(v) = 0 and L(w v ) = 2 and if v ∈ W then L(v) = 5 and L(w v ) = 3. Now for each edge uv of G such that u ∈ B and v ∈ W , we label the vertices of G uv as follows: L

  [START_REF] Fiala | Fixed-parameter complexity of λ-labelings[END_REF] and L(g 2 ) = 5. For each arc uv of D[B], we label the vertices of G uv as follows:L(a u ) = 3, L(a v ) = 5, L(b u ) = 1, L(b v ) = 2, L(c) = 4, L(d) = 0, L(e 1 ) = 2, L(e 2 ) =3, L(e 3 ) = 5, L( f ) = 5, L(g 1 ) = 1 and L(g 2 ) = 0. Analogously, for each arc uv of D[W ], we label the vertices of G uv as follows: L(a u ) = 2, L(a v ) = 0, L(b u ) = 4, L(b v ) = 3, L(c) = 1, L(d) = 5, L(e 1 ) = 3, L(e 2 ) = 2, L(e 3 ) = 0, L( f ) = 0, L(g 1 ) = 4 and L(g 2 ) = 5. It is simple matter to check that L is an L(2, 1)-labelling of H(G).