Rok Erman
email: rok.erman@gmail.com

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

Bernard Lidický
email: bernard@kam.mff.cuni.cz

Ondrej Pangrac
email: pangrac@kam.mff.cuni.cz

AND OND ŘEJ Bernard Lidick Ý §

Pangr Ác

5-COLOURING GRAPHS WITH 4 CROSSINGS *

Keywords: chromatic number, crossing number, clique number, girth

1. Introduction. The crossing number of a graph G, denoted by cr(G), is the minimum number of crossings in any drawing of G in the plane.

The Four Colour Theorem states that, if a graph has crossing number zero, then it is 4-colourable. A natural question is to ask whether the chromatic number of a graph is bounded in terms of its crossing number. To answer the question, the concept of crossing cover is crucial. A crossing cover of a drawing of a graph is a set of vertices C such that every crossing has an edge incident with a vertex in C. If C is a crossing cover, then G -C is planar, so χ(G) ≤ 4 + χ(G C ) ≤ 4 + |C|. Picking one vertex per crossing, we obtain a crossing cover of cardinality at most cr(G) so χ(G) ≤ 4 + cr(G).

This upper bound is tight only for cr(G) ≤ 1. So it is natural to ask for the smallest integer f (k) such that every graph G with crossing number at most k is f (k)colourable? An argument similar to the one above shows that f (k + 1) ≤ f (k) + 1. Settling a conjecture of Albertson [START_REF] Albertson | Chromatic Number, Independence Ratio, and Crossing Number[END_REF], Schaefer [14] showed that f (k) = O k 1/4 . This upper bound is tight up to a constant factor since χ(K n ) = n and cr(K n ) ≤

|E(Kn)| 2 = ( n 2 )
2 ≤ 1 8 n 4 . The values of f (k) are known for a number of small values of k. The Four Colour Theorem states f (0) = 4 and implies easily that f (1) ≤ 5. Since cr(K 5 ) = 1, we have f (1) = 5. Oporowski and Zhao [START_REF] Oporowski | Coloring graphs with crossing[END_REF] showed that f (2) = 5. Since cr(K 6 ) = 3, we have f (3) = 6. Further, Albertson et al. [START_REF] Albertson | Coloring graphs with given crossing patterns[END_REF] showed that f (6) = 6. Albertson then conjectured that if χ(G) = r, then cr(G) ≤ cr(K r ). This conjecture was proved by Barát and Tóth [START_REF] Barát | Towards the Albertson Conjecture[END_REF] for r ≤ 16.

A graph G is r-critical if χ(G) = r and χ(G ) < r for every proper subgraph G of G. Oporowski and Zhao [START_REF] Oporowski | Coloring graphs with crossing[END_REF] proved that K 6 is the unique 6-critical graph with crossing number 3.

Theorem 1.1 (Oporowski and Zhao [START_REF] Oporowski | Coloring graphs with crossing[END_REF]). If cr(G) ≤ 3 and ω(G) ≤ 5, then χ(G) ≤ 5.

Oporowski and Zhao [START_REF] Oporowski | Coloring graphs with crossing[END_REF] asked whether the conclusion remains true even if cr(G) ∈ {4, 5}. Question 1.2 (Oporowski and Zhao [START_REF] Oporowski | Coloring graphs with crossing[END_REF]). If cr(G) ≤ 5 and ω(G) ≤ 5, is G 5-colourable?

We answer in the negative by showing a counterexample. The help of Zdeněk Dvořák was greatly appreciated while obtaining the following theorem.

Theorem 1.3. There exists a graph G such that cr(G) = 5, ω(G) ≤ 5 and χ(G) = 6.

On the other hand, we answer Question 1.2 in the affirmative when cr(G) = 4. Theorem 1.4. If cr(G) ≤ 4 and ω(G) ≤ 5, then χ(G) ≤ 5.

A key notion in the proof of Theorem 1.4 is the one of dependent crossings. The cluster of a crossing is the set of endvertices of its two edges. Two crossings are dependent if their clusters intersects.

Settling a conjecture of Albertson [START_REF] Albertson | Chromatic Number, Independence Ratio, and Crossing Number[END_REF], Král' and Stacho [START_REF] Král | Coloring plane graphs with independent crossings[END_REF] showed the following. Theorem 1.5 (Král' and Stacho [START_REF] Král | Coloring plane graphs with independent crossings[END_REF]). If a graph G has a drawing in the plane in which no two crossings are dependent, then χ(G) ≤ 5.

Loosely speaking, this theorem states that, if the crossings are far apart from each other, then the graph is 5-colourable. On the other hand, if all the crossings are very close, that is if all their clusters share a common vertex, then the graph is also 5-colourable. In the same vein, we show that if the crossings are covered by 2k edges, then the graph is (4 + k)-colourable (Theorem 4.1). In particular, if the crossings are covered by three edges, then the graph is 6-colourable. This bound 6 is tight since cr(K 6 ) = 3 and thus one can remove three edges from K 6 to make it planar. However, by generalizing Theorem 1.1, we show that K 6 is essentially the unique obstruction for such a graph to be 5-colourable.

Theorem 1.6. If ω(G) ≤ 5 and there exists a set F of at most three edges such that G \ F is planar, then χ(G) ≤ 5.

Related open problems are discussed in the final section.

2. Preliminaries.

Drawings of graphs.

A drawing G (in the plane or the sphere) of a graph G = (V, E) consists of a bijection D from V ∪ E into a set Ṽ ∪ Ẽ such that (i) Ṽ is the image of V and a set of distincts points in the plane;

(ii) for any edge e = uv, the element D(e) = ẽ of Ẽ is the image of a continuous injective mapping φ e from [0, 1] to the plane which is simple (i.e. does not intersect itself) such that φ e (0) = D(u), φ e (1) = D(v) and φ e (]0, 1[) ∩ Ṽ = ∅; (iii) every point in the plane is in at most two images of edges unless it is in Ṽ ; (iv) for two distincts edges e 1 and e 2 of E, ẽ1 and ẽ2 intersects in a finite number of points. We shall often confound the vertex and edge sets of a graph with their image in one of its drawings.

A crossing in a drawing of G is a point in the plane minus Ṽ that belongs to two edges. Formally, it is a point of φ e1 (]0, 1[) ∩ φ e2 (]0, 1[) for some edges e 1 and e 2 . A portion of an edge e is a subarc of φ e [0, 1] between two consecutives endpoints or crossings on e. A portion from a to b is called an (a, b)-portion.

A graph is planar if it has a drawing without crossings. An easy consequence of Euler's Formula is the following well known proposition.

Proposition 2.1.

If G is planar, then |E(G)| ≤ 3|V (G)| -6.
A drawing of G is optimal if it minimizes the number of crossings. Note that two edges may intersect several times, in either endvertices or crossings. However, thanks to the two following lemmas, we will only consider nice drawings, i.e. drawings such that two edges intersect at most once. Lemma 2.2. Every graph with crossing number k has a nice drawing with at most k crossings.

Proof. Let G be a graph with crossing number k. Consider an optimal drawing of G that minimizes the number of crossings between edges with a common vertex. Suppose, by contradiction, that two edges e 1 = u 1 v 1 and e 2 = u 2 v 2 intersect at least twice. Let a and b be two points in the intersection of e 1 and e 2 . Without loss of generality we may assume that u 1 , u 2 , v 1 , and v 2 are in the exterior of the closed curve C which is the union of the (a, b)-portion P 1 on u 1 v 1 and the (a, b)-portion P 2 on u 2 v 2 . We may also assume that P 1 contains at least as many crossings as P 2 .

Then one can redraw u 1 v 1 along the (u 1 , a)-portion of e 1 , P 2 , and the (b, v 1 )portion of e 1 slightly in the exterior of C so that e 1 and e 2 do not cross anymore. Doing so, all the crossings of P 1 including a and b (if they were crossings) disappear while a crossing is created per crossings of P 2 distinct from a and b. Since one of {a, b} must be a crossing (there are no parallel arcs), we obtain a drawing with one crossing less, a contradiction.

Similarly, one can show the following lemma.

Lemma 2.3. Every graph with a set F of edges whose deletion results in a planar graph has a nice drawing in which each crossing contains at least one edge from F .

In this paper, we consider only nice drawings. Thus a crossing is uniquely defined by the pair of edges it belongs to. Henceforth, we will often confound a crossing with this set of two edges.

A face of a drawing G is a connected component of the space obtained by deleting Ṽ ∪ Ẽ from the plane. We let F ( G) (or simply F ) be the set of faces of G. We say that a vertex v or a portion of an edge is incident to f ∈ F if v is contained in the closure of f . The boundary of f , denoted by bd(f ) consists of the vertices and maximum (with respect to inclusion) portions of edges incident to it. An embedding of a graph is the set of boundaries of the faces of some drawing of G in the plane.

Lemma 2.4. Up to a permutation of the vertices, there is only one embedding of K 6 using exactly three crossings. (See Figure 2.1.)

Proof. Let A be an embedding of K 6 using three crossings. Let us show that it is unique. First we observe that every edge is crossed at most once. Otherwise, there will be two edges whose removal leaves the graph planar which is a contradiction to Proposition 2.1. As every cluster of a crossing contains four vertices, there must be a vertex v contained in two of them. Note that v cannot be in all three clusters since K 6v (which is isomorphic to K 5 ) is not planar. Let e 1 = vx and e 2 = vy be the two crossed edges adjacent to v and e 3 one of the edges of the crossing whose cluster does not contain v. The graph K 6 \ {e 1 , e 2 , e 3 } is a planar triangulation T where deg(v) = 3.

We denote a, b, c the neighbours of v in T . They must induce a triangle. Without loss of generality, ab and bc are the edges crossed by e 1 and e 2 , respectively.

As T is a triangulation abx and bcy form triangles. Moreover, xby is also a triangle as x and y are consecutive neighbours around b. The last two edges, which are not discussed yet, are xc and ya. They must cross inside bxyc (one of them is e 3 ). Hence A is unique. Lemma 2.5. A drawing of K 5 with all vertices incident to the same face requires 5 crossings.

Proof. Let us number the vertices of K 5 v 1 , v 2 , v 3 , v 4 , v 5 in the clockwise order around the boundary of the face f incident to them. Then free to redraw the edges v 1 v 2 , v 2 v 3 , v 3 v 4 , v 4 v 5 and v 5 v 1 , we may assume that the boundary is the cycle v 1 v 2 v 3 v 4 v 5 and that f is its interior. Now both v 1 v 3 and v 2 v 4 are in the exterior of C and thus must cross. Similarly,

{v 2 v 4 , v 3 v 5 }, {v 3 v 5 , v 4 v 1 }, {v 4 v 1 , v 5 v 2 } and {v 5 v 2 , v 1 v 3 } are crossings.
Lemma 2.6. A drawing of K 2,3 such that vertices of each part are in a common face requires at least one crossing.

Proof. Let ({u 1 , u 2 }, {v 1 , v 2 , v 3 }) be the bipartition of K 2,3 . Suppose by contradiction that K 2,3 has a drawing such that each part of the bipartition is in a common face. Then adding a vertex u 3 is the face incident to the vertices v 1 , v 2 and v 3 and connecting u 3 to those vertices by new edges yields a drawing of K 3,3 with no crossing which contradicts the fact that K 3,3 is not planar.

Properties of 6-critical graphs.

A stable crossing cover of a drawing of a graph is a set of vertices that is both stable and a crossing cover.

Lemma 2.7. Every graph with a stable crossing cover is 5-colourable. Proof. Let G be a graph having a stable crossing cover W . Use the Four Colour Theorem on G -W and extend the colouring to G by using a fifth colour on W .

Let G be a graph and u, v be vertices of G. The operation of identification of u and v in G results in a graph denoted by G/{u, v}, which is obtained from G -{u, v} by adding a new vertex w and the set of edges {wz | uz or vz is an edge of G}.

Lemma 2.8. Let G be a graph and v be a degree five vertex of G. Let u and w be two non-adjacent neighbours of v. If (Gv)/{u, w} is 5-colourable, then so is G.

Proof. A proper 5-colouring of (G-v)/{u, w} corresponds to a proper 5-colouring of Gv such that u and w are coloured by the same colour. So it can be extended to a proper 5-colouring of G by assigning a colour to v.

Let G be a graph and a drawing of it in the plane. A cycle is separating if it has a vertex in its interior and a vertex in its exterior. A cycle C is non-crossed if all its edges are non-crossed. It is regular if any cluster of a crossing containing an edge of C contains at least three vertices of C. Lemma 2.9. In every drawing in the plane of a 6-critical graph there is no separating regular triangle.

Proof. Let G be a 6-critical graph drawn in the plane. Suppose, by way of contradiction, that there is a regular triangle C. Let G 1 be the graph induced by the vertices in C and inside C and let G 2 be a graph induced by the vertices in C and outside C. Since C is separating, both G 1 and G 2 have fewer vertices than G. Hence, by 6-criticality of G, they are 5-colourings of those graphs. In addition, in these colourings of G 1 and G 2 , the colours of the vertices of C are distinct. So, free to permute the colours, one can assume that the two 5-colourings of G 1 and G 2 agree on C. Hence their union yields a 5-colouring of G. Lemma 2.10. Let G be a 6-critical graph distinct from K 6 . In every nice drawing of G, there is no separating triangle such that

• at most one of its edges is crossed, and • there is at most one crossing in its interior. Proof. Suppose, by way of contradiction, that such a cycle C = x 1 x 2 x 3 exists. Then by Lemma 2.9, one of its edges, say x 2 x 3 , is crossed. Let uv be the edge crossing it with u inside C and v outside. By Lemma 2.9, C is not regular, so u = x 1 . Moreover, u / ∈ {x 2 , x 3 } since the drawing is nice. Let G 1 be the graph induced by C and the vertices outside C. Then G 1 admits a 5-colouring c 1 since G is 6-critical.

Let G 2 be the graph obtained from the graph induced by C and the vertices inside C by adding the edges ux 1 , ux 2 and ux 3 if they do not exist. Observe that G 2 has a planar drawing with at most 2 crossings. Indeed the edge ux 1 may be drawn along uv and then a path in the outside of C and the edges ux 2 and ux 3 may be drawn along the edges of the crossing {x 2 x 3 , uv}. Thus G 2 admits a 5-colouring c 2 .

In both colourings, the colours of the vertices of C are distinct. So, free to permute the colours, we may assume that c 1 and c 2 agree on C. One can also choose for u a colour of {1, . . . , 5} \ {c 2 (x 1 ), c 2 (x 2 ), c 2 (x 3 )} so that c 2 (u) = c 1 (v). Then the union of c 1 and c 2 is a 5-colouring of G.

Lemma 2.11. Let G be a 6-critical graph. In every drawing of G in the plane, there is no non-crossed 4-cycle C such that

• C has a chord in its exterior,

• C and its interior is a plane graph, and • the interior of C contains at least one vertex. Proof. Suppose, by way of contradiction, that there is a 4-cycle C = tuvw satisfying the properties above with vt a chord in its exterior. Consider the graph G 1 , which is obtained from G by removing the vertices inside C. Since G is 6-critical, G 1 admits a 5-colouring c 1 in {1, 2, 3, 4, 5}. Without loss of generality, we may assume that c 1 (v) = 5. Hence {c 1 (t), c 1 (u), c 1 (w)} ⊂ {1, 2, 3, 4}. Now consider the graph G 2 which is obtained from G by removing the vertices outside C. If c 1 (u) = c 1 (w), let H be the graph obtained from G 2v by identifying u and w. If c 1 (u) = c 1 (w), let H be the graph obtained from G 2v by adding the edge uw if it does not already exist. In both cases H is a planar graph. Hence H admits a 4-colouring c 2 in {1, 2, 3, 4}. Moreover, by construction of H, c 2 (u) = c 2 (w) if and only if c 1 (u) = c 1 (w). Hence free to permute the colours, we may assume that c 1 and c 2 agree on {t, u, w}.

Hence the union of c 1 and c 2 is a 5-colouring of G.

2.3. 6-critical graphs embeddable on the torus or the Klein bottle. In the proof of Theorem 1.6, we use the list of all 6-critical graphs embeddable on the torus, which was obtained by Thomassen [START_REF] Thomassen | Five-coloring graphs on the torus[END_REF], and the list of all 6-critical graphs embeddable on the Klein bottle, which was obtained independently by Chenette et al. [START_REF] Chenette | Five-coloring graphs in the Klein bottle[END_REF] and Kawarabayashi et al. [START_REF] Kawarabayashi | Lidický: 6-critical graphs on the Klein bottle[END_REF].

Theorem 2.12 (Thomassen [START_REF] Thomassen | Five-coloring graphs on the torus[END_REF]). There are four non-isomorphic 6-critical graphs embeddable on the torus. Three of them are depicted in Figure 2.2 and the last one is a 6-regular graph on 11 vertices.

Theorem 2.13 (Chenette et. al. [4]; Kawarabayashi et al. [START_REF] Kawarabayashi | Lidický: 6-critical graphs on the Klein bottle[END_REF]). There are nine non-isomorphic 6-critical graphs embeddable on the Klein bottle. They are depicted in

H 1 H 2 K 6 v u Fig. 2.2.
The list of 6-critical graphs embeddable on the Klein bottle. The first three of them are embeddable on torus as well.

Lemma 2.14. If three edges are deleted a 6-critical graph embeddable on the torus other than K 6 , then the resulting graph is nonplanar.

Proof. We know the complete list of graphs which must be checked due to Theorem 2.12. For all of them except K 6 , we have |E| > 3|V | -3. Thus the graphs are not planar after removing three edges according to Proposition 2.1.

Lemma 2.15. If three edges are deleted a 6-critical graph embeddable on the Klein bottle other than K 6 , then the resulting graph is nonplanar.

Proof. We know the complete list of graphs which must be checked due to Theorem 2.13. For all of those graphs except K 6 , H 1 and H 2 , we have |E| > 3|V |-3. Thus those graphs are not planar after removing three edges according to Proposition 2.1. Now we need to deal with the last two graphs H 1 and H 2 , see Figure 2.2. Let us first examine H 1 . It contains two edge disjoint copies of K 6 without one edge. Each of these copies needs at least two edges to be removed by Proposition 2.1, so H 1 needs at least four edges to be removed.

Let us now examine H 2 . Let F be a set of edges such that H 2 \ F is planar. Let us denote by u and v the two vertices of the only 2-cut of H 2 , see Figure 2.2. Observe that H 2 -{u, v} is a disjoint union of K 5 and K 4 . Since K 5 is not planar, one edge e of this K 5 is in F . But there is still a (u, v)-path P in K 5 \ e. Then the union of the graph induced by u, v, the vertices of the K 4 and the path P is a subdivision of K 6 . Thus, by Proposition 2.1 for K 6 , at least three of its edges must be in F . Thus |F | ≥ 4.

3. 6-critical graph of crossing number 5. We prove Theorem 1.3 by exhibiting a drawing of a 6-critical graph G using 5 crossings which is not K 6 .

Theorem 3.1. The graph G depicted in Figure 3.1 is 6-critical. Proof. We show by contradiction that G is not 5-colourable. We refer the reader to Figure 3.1 for names of vertices. Assume that is a 5-colouring of G. As vertices u, v and w form a triangle, they must get distinct colours. Without loss of generality, assume that (u) = 1, (v) = 2 and (w) = 3. The vertices a and b are adjacent to each other and to all the vertices of the triangle uvw, hence { (a), (b)} = {4, 5}. Thus (c) = 3 as c is adjacent to a, b, u and v. By symmetry we obtain that (d) is also 3, which is a contradiction since cd is an edge.

It can be easily checked that every proper subgraph of G is 5-colourable. So G is 6-critical. Proof. We procced by induction on k. The result holds when k = 0 by the Four Colour Theorem.

Suppose that the result is true for k. Let G = (V, E) be a graph with a set F of at most 2k + 2 edges such that G \ F is planar. Without loss of generality, we may assume that F is minimal, i.e. for any proper subset F ⊂ F , the graph G \ F is not planar.

Consider a planar drawing of G \ F . It yields a drawing of G such that each crossing contains an edge of F .

Suppose that |F | ≤ 2k + 1. Let e = uv be an edge of F . By the induction hypothesis,

G -v is (4 + k)-colourable because F \ e is a set of 2k edges whose removal leaves G -v planar. Hence χ(G) ≤ χ(G -v) + 1 ≤ 4 + k + 1.
So we may assume that |F | = 2k + 2.

If two edges e and f of

F have a common vertex v, then G -v is (4 + k)- colourable because F \ {e, f } is a set of 2k edges whose removal leaves G -v planar. So χ(G) ≤ χ(G -v) + 1 ≤ 4 + k + 1.
So we may assume that the edges of F are pairwise non-adjacent.

Let e = {u 1 , u 2 } and f = {v 1 , v 2 } be two edges in F . Then the endvertices of these two edges induce a K 4 . Suppose for contradiction that u 1 and v 1 are not adjacent. Then G -{u 1 , v 1 } is (4 + k)-colourable because F \ {e, f } is a set of 2k edges whose removal leaves G -{u 1 , v 1 } planar and u 1 and v 1 can get the same colour. So

χ(G) ≤ χ(G -{u 1 , v 1 }) + 1 ≤ 4 + k + 1. Hence X = {u 1 , u 2 , v 1 , v 2 } induces a K 4 .
We further distinguish two possible cases:

k = 0: Let the edges of F be e = {u 1 , u 2 } and f = {v 1 , v 2 } and let X = {u 1 , u 2 , v 1 , v 2 }.
Let C be the 4-cycle induced by X in the plane graph G \ {e, f }. Note that C is a separating cycle, otherwise G \ e would be planar. We cut G along C and obtain two smaller graphs G 1 and G 2 , where both of them contain X.

We 5-colour them by induction. A colouring of G can be then obtained from the 5-colourings of G 1 and G 2 by permuting colours on X so that the these two colourings agree on V (C). k ≥ 1: Note that union of all endvertices of edges from F induce a complete graph

K 2|F | . A K 2|F | must
|E| ≤ 3|V | -6 + 2k + 2 4k + 4 2 ≤ 3(4k + 4) + 2k -4 8k 2 -2 ≤ 0
Hence this case is not possible.

Since cr(K 5 ) = 1 and cr(K 6 ) = 3, Theorem 4.1 is tight when k ≤ 2. But K 6 is the only obstacle for pushing the result further as shown by the following theorem which is a reformulation of Theorem 1.6 in terms of critical graphs.

Theorem 4.2. If at most three edges are deleted from a 6-critical graph other than K 6 , then the resulting graph is nonplanar.

Proof. Let G be a 6-critical graph distinct from K 6 and F a set of at most three edges. Assume for a contradiction that G \ F is planar.

Let us consider a nice drawing of G. By Lemma 2.7, G has no stable crossing cover.

If |F | ≤ 2, then Theorem 4.1 contradicts the fact that G is not 5-colourable. Hence we assume that F = {e 1 , e 2 , e 3 }. Set e i = u i v i for i ∈ {1, 2, 3}.

Claim 1. The three edges of F are pairwise vertex-disjoint.

Proof. If there is a vertex v shared by all three edges, then {v} is a stable crossing cover, a contradiction. Hence a vertex u is shared by at most two edges of F . Let s be the number of degree two vertices in the graph induced by F .

We now derive a contradiction for each value of s > 0. So s = 0, which proves the claim. s = 1: Without loss of generality, u = u 1 = u 2 . None of {u, u 3 } and {u, v 3 } is a stable crossing cover so uu 3 and uv 3 are edges. We redraw the edge e 3 along the path u 3 uv 3 such that it crosses only edges incident to u. See Figure 4.1(A). Then u is a stable crossing cover, a contradiction. s = 2: Without loss of generality, u = u 1 = u 2 and v = v 2 = v 3 . Then F induces a path. None of {v 1 , v} and {u, u 3 } is a stable crossing cover, so v 1 v and uu 3 are edges. We add a handle between vertices u and v. Then we draw edges of F using the handle, see Figure 4.1(B). Hence G can be embedded on the torus, which is a contradiction to Lemma 2.14. s = 3: Without loss of generality, u = u 1 = u 2 is one of the shared vertices. Let v and w be the other two. Note that F induces a triangle. By Proposition 2.1, we have |E(G)| ≤ 3|V (G)| -3. Hence there must be at least 6 vertices of degree five as the minimum degree of G is five. Let x be a degree five vertex different from u, v and w. By minimality of G, there exists a 5-colouring of Gx. Free to permute the colours, we may assume that (u) = 1, (v) = 2 and (w) = 3. Moreover, the neighbours of x are coloured all differently. We denote by y and z the neighbours of x, which are coloured 4 and 5 respectively. We assume that G is embedded in the plane such that all crossings are covered by F . There are two consecutive neighbours of x in the clockwise order such that they have colours in {1, 2, 3}. We denote these vertices by a and b. Without loss of generality let the clockwise order around x be z, y, a, b and (a) = 1 and (b) = 2. See Figure 4.

1(C).

Let A be the connected component of a in the graph induced by the vertices coloured 1 and 5. If A does not contain z, we can switch colours on it. Then x can be coloured by 1 and we have a contradiction. Note that the colour switch is correct even if u is in A because the new colour of u will be 5 which different from 2 and 3. Thus there must be a path between a and z of vertices coloured 1 and 5. A similar argument shows that there is a path between b and y of vertices coloured 2 and 4. These paths must be disjoint and they are not using edges of F . But they cannot be drawn in the plane without crossings, a contradiction.

Claim 2. For any distinct integers i, j ∈ {1, 2, 3}, an endvertex of e i is adjacent to at most one endvertex of e j .

Proof. Suppose not. Then without loss of generality, we may assume that u 2 is adjacent to u 1 and v 1 . First we redraw the edge e 1 along the path u 1 u 2 v 1 . Then every edge crossed by e 1 , which is not e 3 , is incident to e 2 . Since {u 2 , u 3 } and {u 2 , v 3 } are not stable crossing covers, u 2 u 3 and u 2 v 3 are edges. We redraw e 3 along the path u 3 u 2 v 3 . Then, again, every edge crossed by e 3 , which is not e 1 , is incident to e 2 . Moreover, the edges e 1 and e 3 cross otherwise {u 2 } would be a stable crossing cover. See Figure 4.1(D).

We distinguish several cases according to the number p of neighbours of v 2 among u 1 , v 1 , u 3 and v 3 . p = 0: The vertex v 2 and a pair of two non-adjacent vertices among u 1 , v 1 , u 3 and v 3 would form a stable crossing cover. Hence {u 1 , v 1 , u 3 , v 3 } induces a K 4 . See Figure 4.1(E). By Lemma 2.9, there is no vertex inside each of the triangles

u 2 u 1 u 3 , u 2 u 3 v 1 , u 2 v 1 v 3 and u 2 u 1 v 3 .
Hence all the vertices are inside the 4cycle

u 1 u 3 v 1 v 3 . It includes the vertex v 2 .
We redraw e 1 such that it is crossing only e 3 and u 2 v 3 . Then {v 3 , v 2 } is a stable crossing cover, a contradiction. See Figure 4.1(F). p = 1: Without loss of generality we may assume that the neighbour of v 2 is u 1 .

None of {v 2 , v 1 , u 3 } and {v 2 , v 1 , v 3 } is a stable crossing cover so u 3 v 1 and v 1 v 3 are edges. By Lemma 2.9, there is no vertex inside each of the triangles u 2 u 3 v 1 and u 2 v 1 v 3 . See Figure 4.1(G). Thus the edge e 3 could be drawn inside these triangles and the set F can be changed to F = {e 1 , e 2 , u 2 v 1 }. Two edges of F share an endvertex which is a contradiction to Claim 1. p ∈ {2, 3}: We further distinguish two sub-cases. Either two neighbours of v 2 in {u 1 , v 1 , u 3 , v 3 } are joined by an edge of F or not. In the second case, without loss of generality, we may assume that the vertices adjacent to v 2 are u 1 and v 3 . Now by Lemma 2.11 there is no vertex inside the 4-cycle v 2 u 1 u 2 v 3 . Hence e 2 can be drawn inside this cycle. See Figure 4.1(H). Since the removal of {e 1 , e 3 } does not make G planar,

v 1 u v 2 u 3 v 3 (A) v 1 u v u 3 (B) x a b y z (C) u 1 v 1 u 2 v 2 u 3 v 3 (D) u 1 v 1 u 2 v 2 u 3 v 3 (E) u 1 v 1 u 2 v 2 u 3 v 3 (F ) u 1 v 1 u 2 v 2 u 3 v 3 (G) u 1 v 1 u 2 v 2 u 3 v 3 (H) u 1 v 1 u 2 v 2 u 3 v 3 (I) u 1 v 1 u 2 v 2 u 3 v 3 (J)
v 1 v 3 is inside v 2 u 1 u 2 v 3 .
Hence the set F = {e 1 , e 3 , u 1 v 3 } contradicts Claim 1.

In the first case, we may assume Without loss of generality, that v 2 is adjacent to u 1 and v 1 . We first redraw e 1 along the path u 1 v 2 v 1 . Now all the edges crossing e 1 are incident to v 2 . Thus {v 2 , u 3 } or {v 2 , v 3 } form a stable crossing cover. See Figure 4.1(I). p = 4: See Figure 4.1(J). We repeatedly use Lemma 2.11 which implies that the 4cycles

u 2 u 3 v 2 u 1 , u 2 u 3 v 2 v 1 , u 2 v 1 v 2 v
3 and u 2 v 3 v 2 u 1 are not separating. This means that the graph contains only six vertices. This is a contradiction because the unique 6-critical graph on six vertices is K 6 .

Since {u 1 , u 2 , u 3 } is not a stable crossing cover, it must induce at least one edge, say u 1 u 2 . Then Claim 2 implies that u 1 v 2 and v 1 u 2 are not edges. Now {v 1 , u 2 , u 3 } and {v 1 , u 2 , v 3 } are not stable crossing covers. Thus, by symmetry, we may assume that u 2 u 3 and v 1 v 3 are edges. {u 1 , v 2 , u 3 } is not a stable crossing cover so u 1 u 3 is an edge; {v 1 , v 2 , u 3 } is not a stable crossing cover so v 1 v 2 is an edge; {u 1 , v 2 , v 3 } is not a stable crossing cover so v 2 v 3 is an edge. Hence there are two triangles u 1 u 2 u 3 and v 1 v 2 v 3 , which are not separating by Lemma 2.9.

Without loss of generality, two possibilities occur. Either the edges of F do not cross each other or one pair of them is crossing. If they do not cross (Figure 4.2(A)), G can be embedded on the torus by adding a handle into the triangles and drawing the edges of F on the handle, which contradicts Lemma 2.14. If they cross (Figure 4.2(B)), it is possible to draw G on the Klein bottle, see Figure 4.2(C), which contradicts Lemma 2.15.

u 1 v 1 u 2 v 2 u 3 v 3 (A) u 1 v 2 u 2 v 1 u 3 v 3 (B) u 1 v 2 u 2 v 1 u 3 v 3 (C)
5. 5-colouring graphs with 4 crossings. In this section we prove the following Theorem 5.1, which is a reformulation of Theorem 1.4 in terms of critical graphs.

Theorem 5.1. The unique 6-critical graph with crossing number at most 4 is K 6 .

Proof. Suppose, by way of contradiction, that G = (V, E) is a 6-critical graph with crossing number at most 4 distinct from K 6 . Moreover, one may assume that G is such a critical graph with the minimum number of vertices and with the maximum number of edges on |V (G)| vertices.

Moreover, assume that we have a nice optimal drawing of G. By Theorem 1.6, there are four crossings and every edge is crossed at most once.

Since G is 6-critical, every vertex has degree at least 5. By Proposition 2.1, we have |E| ≤ 3|V | -6 + cr(G) ≤ 3|V | -2. Hence there are at least four vertices of degree 5.

Let v be an arbitrary degree five vertex and v i , 1 ≤ i ≤ 5 be the neighbours of v in the counterclockwise order around v. By criticality of G, the graph Gv admits a 5-colouring φ. Necessarily, all the v i are coloured differently, otherwise φ could be extended to v.

For any i ≤ j, there is a path, denoted by v iv j , from v i to v j such that all its vertices are coloured in φ(v i ) or φ(v j ). Otherwise, v j is not in the connected component A of v i in the graph induced by the vertices coloured φ(v i ) and φ(v j ). Hence by exchanging the colours φ(v i ) and φ(v j ) on A, we obtain a 5-colouring φ of Gv such that no neighbour of v is coloured φ(v i ). Hence by assigning φ(v i ) to v we obtain a 5-colouring of G, a contradiction.

Let q be the number of crossed edges incident to v. Claim 3. q = 0. Proof. The union of the v iv j , for i = j, is a subdivision of K 5 in Gv. If q = 0, then the v i , 1 ≤ i ≤ 5, are in one face after the removal of v. By Lemma 2.5, such a subdivision requires 5 crossings which contradicts the assumption of at most four crossings.

Claim 4. q = 1.

Proof. Suppose to the opposite that q = 1. Without loss of generality, we may assume that the crossed edge is vv 1 .

The path v 2v 4 must cross the two paths v 1v 3 and v 3v 5 . Since every edge is crossed at most once, then v 2 v 4 is not an edge.

Let G be the graph obtained from Gv by identifying v 2 and v 4 into a new vertex v . By Lemma 2.8, G is not 5-colourable. Now G has at most three crossings because we removed the crossed edge vv 1 together with v. So, by minimality of G, the graph G contains a subgraph H isomorphic to K 6 . Moreover, H must contain v since G contains no K 6 . Since G has only three crossings we can use Lemma 2.4. Let u 1 and u 2 be vertices of H which form a triangular face together with v and let u 3 , u 4 and u 5 be the vertices forming the other triangular face. Without loss of generality, we may assume that u 3 u 4 u 5 is inside v u 1 u 2 as in Figure 5.1(A).

Let us now consider the situation in G. Instead of discussing many rotations of K 6 we rather fix K 6 and try to investigate possible placings of v and its neighbours. We denote the neighbours of v which were identified by x and y (i.e. {v 2 , v 4 } = {x, y}). Let a and b be the two other neighbours of v such that va and vb are not crossed ({a, b} = {v 3 , v 5 }). Moreover, we assume that in the counterclockwise order around v, the sequence is x, a, y, b. Note that the vertex v 1 may be inserted anywhere in the sequence.

One of the identified vertices, say x, is adjacent to at least two vertices of {u 3 , u 4 , u 5 }.

1) Assume first that x is adjacent to u 3 ,u 4 and u 5 . Then since G has no K 6 , it is not adjacent to some vertex in {u 1 , u 2 }, say u 2 . Thus yu 2 ∈ E. The vertex a is either inside u 2 yvx or is u 2 . See In both cases, one of the paths v 1x and v 1y must cross ab. But there are no more crossings available. This completes the proof of Claim 4.

Claim 5. q = 2.

Proof. Suppose to the opposite that q = 2.

We first prove the following assertion that will be used several times. Assertion Let x and y be two neighbours of v. Then x and y are adjacent if one of the following holds:

• vx and vy are not crossed;

• {x, y} is included in the cluster of some crossing. Observe that Gv has at most two crossings. Suppose that x and y are not adjacent. If vx and vy are not crossed, we can identify x and y along xvy without adding any new crossing. If {x, y} is included in the cluster of some crossing, we can identify x and y along the edges of this crossing without adding any new crossing. Hence in both cases (Gv)/{x, y} has a planar drawing with at most 2 crossings. Then Lemma 2.8 and Theorem 4.1 yield a contradiction. This proves the Assertion.

Assume that the crossed edges are consecutive, say vv 1 and vv 2 . By the Assertion, v 3 v 5 is an edge. See Figure 5.2(A). If v 3 v 5 is not crossed or crosses either vv 1 and vv 2 , then the cycle vv 3 v 5 is regular, which contradicts Lemma 2.9. If v 3 v 5 is crossed by another edge, then the cycle vv 3 v 5 contradicts Lemma 2.10. Henceforth, we may assume that the two crossed edges are not consecutive, say vv 2 and vv 5 . By the Assertion, v 1 v 3 , v 1 v 4 and v 3 v 4 are edges. If v 1 v 3 is not crossed, then the triangle vv 1 v 3 is separating because v 2 and v 4 are on the opposite sides. This contradicts Lemma 2.9. If v 1 v 3 is crossed it can be redrawn along the path v 1 vv 3 with one crossing with vv 2 . Symmetrically, we assume that v 1 v 4 is crossing vv 5 . See Figure 5.2(B).

v v 1 v 2 v 3 v 4 v 5 (A) v v 1 v 2 v 3 v 4 v 5 (B) v v 1 v 2 v 3 v 4 v 5 (C) v v 1 v 2 v 3 v 4 v 5 u (D) v v 1 v 2 v 3 v 4 v 5 u (E) v v 1 v 2 v 3 v 4 v 5 u (F ) v v 1 v 2 v 3 v 4 v 5 u (G)
By the Assertion, A vertex u is a candidate if it is not adjacent to v. There is no candidate u common to both C and D otherwise {u, v} would be a stable crossing cover. There are no non-adjacent candidate vertices c ∈ C and d ∈ D otherwise {v, c, d} would be a stable crossing cover.

{v 1 v 2 , v 2 v 3 , v 4 v 5 , v 5 v 1 } ⊂ E(G). See
Assume that a(D) = 4. The vertex v 1 cannot be in D because it is already adjacent to all the other neighbours of v by edges not in D. Thus D = {v 2 , v 3 , v 4 , v 5 }. But then, by the Assertion, v 2 v 5 is an edge. So N (v) ∪ {v} induces a K 6 , a contradiction. Hence a(C) ≤ a(D) ≤ 3.

Suppose now that X ∈ {C, D} does not induce a K 4 . Then two vertices x 1 and x 2 of X are not adjacent. One can add the edge x 1 x 2 and draw it along the edges of the crossing such that no new crossing is created. Hence by the choice of G, the obtained graph G ∪ x 1 x 2 contains a K 6 . Since K 6 has crossing number 3, one of the crossings containing v in its cluster must be used. So v belongs to the K 6 and hence the K 6 is induced by {v} ∪ N (v). In such case edges v 2 v 4 and v 3 v 5 cross and hence form C or D, which is not possible since a(C) ≤ a(D) ≤ 3.

Hence both C and D induce a The set {v 2 , v 4 } is stable and covers the three crossings distinct from C. Hence {v 2 , v 4 } does not intersect C, otherwise it would be a stable crossing cover. So C ∩ N (v) ⊂ {v 1 , v 3 , v 5 }. The edge v 1 v 5 is not crossed, otherwise it could be redrawn along the edges of the crossing {vv 5 , v 1 v 4 } to obtain a drawing of G with fewer crossings. Furthermore, v 1 v 3 and v 3 v 5 are not in C because they are in some other crossing. Hence a(C) ≤ 2.

Let B be the set of candidates of C. Recall that all vertices of B are adjacent to u. Moreover, every vertex b ∈ B is adjacent to a vertex of {v 2 , v 4 } otherwise {v 2 , v 4 , b} is a stable crossing cover. But v 4 and u are separated by v 3 v 4 v 5 , so all vertices of B are adjacent to v 2 . Now the graph induced by the edges between B and {u, v 2 } is a complete bipartite graph. Moreover, its induced drawing has no crossing and the vertices of each part are in a common face. Thus, by Lemma 2.6, |B| ≤ 2. So a(C) = 2.

Recall that C ∩ N (v) ⊂ {v 1 , v 3 , v 5 }. Suppose that C ∩ N (v) = {v 1 , v 3 }. The closed curve formed by the path v 3 vv 1 and the two"half-edges" connecting v 1 to v 3 in C separates v 2 and u. Then the vertices of B cannot be adjacent to both u and v 2 , a contradiction. Similarly, we obtain a contradiction if C ∩ N (v) = {v 3 , v 5 }. Hence we may assume that C ∩ N (v) = {v 1 , v 5 }. But then connecting the vertices of B to those of {v 2 , v 4 } would require one more crossing. See Figure 5.2(G).

This completes the proof of Claim 5.

Claim 6. q = 3.

Proof. Suppose that q = 3.

Let C be the crossing whose cluster does not contain v. It contains no candidate u otherwise {u, v} would be a stable crossing cover. Hence C ⊂ N (v).

Assume first that the three crossed edges incident to v are consecutive, say the crossed edges are vv 1 , vv 2 and vv 5 . By the Assertion, v 3 v 4 is an edge. See Figure 5.3(A). Up to symmetry, the cluster of C is one of the following three sets The interiors of the cycles vv 2 v 3 , vv 3 v 4 and v 2 v 3 v 4 contain no vertices by Lemma 2.9. Hence v 3 is a degree five vertex. Moreover, its two neighbours u and v are not adjacent and (Gv 3 )/{u, v} has at most two crossings. Then Theorem 4.1 and Lemma 2.8 yield a contradiction.

{v 1 , v 2 , v 3 , v 4 } or {v 2 , v 3 , v 4 , v 5 } or {v 1 , v 2 , v 4 , v 5 }. v v 1 v 2 v 3 v 4 v 5 (A) v v 1 v 2 v 3 v 4 v 5 (B) v v 1 v 2 v 3 v 4 v 5 u (C)
• C = {v 1 , v 2 , v 4 , v 5 }. The crossing C is neither {v 1 v 2 , v 4 v 5 } nor {v 1 v 5 , v 2 v 4 }
since it is impossible to draw so that every edge is crossed exactly once. Hence C = {v 1 v 4 , v 2 v 5 }. By the Assertion, v 2 v 4 ∈ E(G). Then the triangle vv 2 v 4 contradicts Lemma 2.10. Suppose now that the three crossed edges incident to v are not consecutive. Without loss of generality, we assume that these edges are vv 1 , vv 3 and vv 4 .

By the Assertion, v 2 v 5 is an edge. If v 2 v 5 is not crossed, then vv 2 v 5 is a separating triangle, contradicting Lemma 2.9. So v 2 v 5 is crossed. It could not cross vv 3 nor vv 4 otherwise vv 2 v 5 would be a regular cycle contradicting Lemma 2.9. Moreover, v 2 v 5 cannot be in C otherwise vv 2 v 5 would contradict Lemma 2.10. Hence v 2 v 5 crosses vv 1 .

By the Assertion, v 1 v 2 and v 1 v 5 are edges. Moreover they are not crossed, otherwise they could be redrawn along the edges of the crossing {vv 1 , v 2 v 5 } to obtain a drawing of G with fewer crossings. See Figure 5 If v 2 v 4 is also an edge, the Assertion implies that v 2 v 3 is also an edge. Then N (v) ∪ {v} induces a K 6 , a contradiction. Hence v 2 v 4 / ∈ E(G). By Lemma 2.10, the cycle vv 4 v 5 is not separating, so its interior contains no vertex and vv 4 is crossed by an edge with v 5 as an endvertex. Let z be the other endvertex of this edge. As an edge is crossed at most once, z is inside vv 3 v 4 . See Figure 5.4(D).

.4(A). v v 1 v 2 v 3 v 4 v 5 (A) v v 1 v 2 v 3 v 4 v 5 (B) v v 1 v 2 v 3 v 4 v 5 (C) v v 1 v 2 v 3 v 4 v 5 z (D) v v 1 v 2 v 3 v 4 v 5 z (E)
Let ab be the edge which is crossing vv 3 . The sets {v 5 , a} and {v 5 , b} are not stable otherwise they would be a stable crossing cover. Hence v 5 a and v 5 b are both edges. Thus ab = v 2 z. See Figure 5.4(E). Now v 1 z is not an edge and hence {v 1 , z} is stable crossing cover, contradicting Lemma 2.7.

This completes the proof of Claim 6. Claim 7. q = 4 Proof. By way of contradiction, suppose that q = 4. Then {v} is a stable crossing cover, a contradiction.

Combining Claims 3, 4, 5, 6 and 7 yields a contradiction. This finishes the proof of Theorem 5.1.

6. Further research.

6.1. Extending our results. Theorem 4.1 states that, if a graph can be made planar by removing at most 2k edges, then it is (4 + k)-colourable. We believe that this is not tight. Thus a natural question is the following: Problem 6.1. What is the maximum chromatic number of all graphs that contain a set of at most k edges whose deletion results in a planar graph?

Let us denote this maximum by g(k). Clearly, g(1) = g(2) = 5 by Theorem 4.1 and because K 5 is not planar and g(3) = 6 by Theorem 4.1 and because cr(K 6 ) = 3. For larger value of k, we also believe that the optimal value is given by a complete graph. It is also very likely that the complete graph K g(k) is the unique g(k)-critical graphs that can be made planar by removing k edges. It is in particular the case for k = 6 and k = 7. Indeed by Proposition 2.1, at least 6 edges are needed to make K 7 planar and there is a set of 6 edges whose removal leaves K 7 planar. See Figure 6.1. Theorem 6.2. Let G be a graph with clique number at most 6. If there is a set of at most 7 edges whose deletion results in a planar planar, then G is 6-colourable.

Proof. To prove this theorem, we show that K 7 is the unique 7-critical graph G for which there exists a set of at most 7 edges whose removal leaves G planar. A famous result of Dirac [START_REF]Dirac: A theorem of R. L. Brooks and a conjecture of Hadwiger[END_REF] states that, if G is r-critical graph and is not K r , then 2|E(G)| ≥ (r -1)|V (G)| + r -3. In particular, if r = 7, then |E(G)| ≥ 3|V (G)| + 2. Hence by Proposition 2.1, we need to remove at least 8 edges to make it planar.

One of the first problem to tackle is the following conjecture which extends both Theorem 1.6 and Theorem 1.4. Conjecture 6.3. Every graph with clique number at most 5 and that contains a set of at most four edges whose deletion results in a planar graph is 5-colourable.

6.2. Critical graphs and colourability. It is easy to derive from Proposition 2.1 that for r ≥ 8, there are only finitely many r-critical graphs that can be embedded on a fixed surface. As pointed out by Thomassen in [START_REF] Thomassen | Five-coloring graphs on the torus[END_REF], the number of 7-critical graphs that can be embedded on a fixed surface is also finite. Finally, Thomassen [START_REF] Thomassen | Color-critical graphs on a fixed surface[END_REF] completed the results by showing that the number of 6-critical subgraphs is finite for any fixed surface Σ. This implies in particular that the (r -1)colourability problem for graphs embeddable on Σ is decidable in polynomial time for any r ≥ 6. On the other hand, deciding 3-colourability is NP-complete for planar graphs (see [START_REF] Garey | Computers and intractability. A guide to the theory of NPcompleteness[END_REF]) and thus also for graphs embeddable on any other surface. The complexity of 4-colourability remains open. Problem 6.4. For any fixed surface, does there exists a polynomial time algorithm for deciding if a graph embeddable on this surface is 4-colourable?

The answer to Problem 6.4 is only known for the sphere by the Four Colour Theorem. An affirmative answer cannot be obtained in the same way as for r -1 ≥ 5 because there are infinitely many 5-critical graphs as implied by a result of Fisk [START_REF] Fisk | The non-existence of colorings[END_REF].

If cr(G) = k, then G is embeddable in S k and in N k as well, where S k is an orientable surface of genus k and N k is a non-orientable surface of genus k. Hence for any k and r ≥ 6, the number of r-critical graphs of crossing number k is finite and so the (r -1)-colourability problem for graphs of crossing number k is decidable in polynomial time. However, the design of such a polynomial time algorithm requires the knowledge of the list of 6-critical graphs. Problem 6.5. Let k ≥ 0. What is the list of 6-critical graphs with crossing number at most k?

When k ≤ 3, the list is empty and if k = 4, then the list is {K 6 }. If k = 5, then the list contains K 6 and the graph depicted in Figure 3.1. But are there any other?

Similarly to graphs embeddable on a fixed surface, the complexity of 4-colourability problem for graphs with crossing number k is not known. Problem 6.6. Let k ≥ 1. Does there exists a polynomial time algorithm for deciding if a given graph with crossing number k is 4-colourable?

This would be true if there were a finite number 5-critical graphs with crossing number at most k. However, as observed by Zdeněk Dvořák, this is not the case. Indeed, every graph obtained from an odd cycle by adding two new vertices adjacent to all the vertices of the cycle and adjacent to each other is 5-critical.

Choosability.

A list assignment of a graph G is a function L that assigns to each vertex v ∈ V (G) a list L(v) of available colours. An L-colouring is a function ϕ : V (G) → v L(v) such that ϕ(v) ∈ L(v) for every v ∈ V (G) and ϕ(u) = ϕ(v) whenever u and v are adjacent vertices of G. If G admits an L-colouring, then it is L-colourable. A graph G is k-choosable if it is L-colourable for every list assignment L such that |L(v)| ≥ k for all v ∈ V (G). The choose number of G, denoted by ch(G), is the minimum k such that G is k-choosable.

Fig. 2 . 1 .

 21 Fig. 2.1. Drawing of K 6 with three crossings.

Figure 2 . 2 .

 22 |V | = 8, |E| = 23 |V | = 9, |E| = 26 |V | = 10, |E| = 28 |V | = 10, |E| = 32 |V | = 10, |E| = 28 |V | = 10, |E| = 28

Fig. 3 . 1 .

 31 Fig. 3.1. A 6-critical graph of crossing number 5.

4 .

 4 Colouring graphs whose crossings are covered by few edges. Theorem 4.1. If a graph can be made planar by deleting a set of at most 2k edges, then G is (4 + k)-colourable.

Fig. 4 . 1 .

 41 Fig. 4.1. The three black edges are covering all the crossings.

Fig. 4 . 2 .

 42 Fig. 4.2. The last case of Theorem 1.6.

Figure 5 . 1 (Fig. 5 . 1 .

 5151 Fig. 5.1. K 6 when identifying two neighbours of v.

Fig. 5 . 2 .

 52 Fig. 5.2. Two crossed edges.

Figure 5 . 2 (

 52 C). Let C = {c 1 c 2 , c 3 c 4 } and D = {d 1 d 2 , d 3 d 4 } be the two crossings not having v in their cluster. For convenience and with a slight abuse of notation, we denote by C (resp. D) both the crossing C (resp. D) and its cluster. For X ∈ {C, D}, let a(X) := |X ∩ N (v)|. Without loss of generality, we may assume that a(C) ≤ a(D).

K 4 .

 4 Thus the candidates in C ∪D induce a complete graph. So there are at most five of them. Since C ∩ D contains no candidate, we have a(C) + a(D) ≥ 3 and so 2 ≤ a(D) ≤ 3 Assume that a(D) = 2 and thus 1 ≤ a(C) ≤ 2. Then C (resp. D) contains a set C (resp. D ) of two candidates. All the vertices of C are adjacent to all the vertices of D . But since both C and D contain a vertex in N (v), drawing all the edges between these two sets requires one more crossing, a contradiction. Hence a(D) = 3. Thus, an edge of D has its two endvertices in N (v) and so it is v 2 v 5 , v 2 v 4 or v 3 v 5 . Let u be the unique candidate of D. Assume first that v 1 ∈ D. Then v 1 u is an edge of D. Moreover, C must be on the paths v 2v 4 and v 3v 5 . Since edges are crossed at most once D = {v 1 u, v 2 v 5 }. Let w be a candidate vertex in C. Then w is outside the cycle vv 2 v 5 . But the only neigbour of v 1 outside this cycle is u which is distinct from w because the crossings C and D have no candidate vertex in common. Thus {w, v 1 } is a stable crossing cover, a contradiction to Lemma 2.7. So v 1 / ∈ D. By symmetry, we may assume that D is either {v 3 v 5 , v 4 u} (Figure 5.2(D)) or {v 3 v 5 , v 2 u} (Figure 5.2(E)) or {v 2 v 5 , v 3 u} (Figure 5.2(F)). In the second and third cases, Lemma 2.10 is contradicted by the cycle v 3 v 4 v 5 and v 1 v 2 v 5 respectively. Hence D = {v 3 v 5 , v 4 u}.

Fig. 5 . 3 .

 53 Fig. 5.3. Three consecutive crossed edges. • C = {v 1 , v 2 , v 3 , v 4 }. Then the edges of C are not v 1 v 4 and v 2 v 3 because it is impossible to draw them such that each is crossed exactly once. Hence C = {v 1 v 3 , v 2 v 4 }. The Jordan curve formed by the path v 1 vv 4 and the two "half-edges" connecting v 1 to v 4 in C separates {v 2 , v 3 } and v 5 . See Figure 5.3(B). Moreover, it is crossed only once (on edge v 1 v), while two crossings are needed, one for each of the disjoint paths v 2v 5 and v 3v 5 , a contradiction. • C = {v 2 , v 3 , v 4 , v 5 }. Then the edges of C are not v 2 v 3 and v 4 v 5 because it is impossible to draw them such that each is crossed exactly once. Hence C = {v 2 v 4 , v 3 v 5 }. Hence by the Assertion, v 2 v 3 , v 4 v 5 and v 2 v 5 are edges.The triangle vv 2 v 3 has only one crossed edge. So, by Lemma 2.10, it is not separating. Thus its interior is empty and the edge crossing vv 2 is incident to v 3 . Let u be the second endvertex of this edge. By symmetry, the interior of vv 4 v 5 is empty and the edge crossing vv 5 is v 4 t for some vertex t.If u = t = v 1 , then by the Assertion v 1 v 2 and v 1 v 5 are edges. So N (v) ∪ {v} induces a K 6 , a contradiction. Hence without loss of generality we may assume that u = v 1 . See Figure5.3(C).

Fig. 5 . 4 .

 54 Fig. 5.4. Three non-consecutive crossed edges. Consider the paths v 2v 4 and v 3v 5 . If they cross, it is through C. Since C ⊂ N (v), the paths v 2v 4 and v 3v 5 are actually edges. See Figure 5.4(B). But one can redraw v 2 v 5 along the edges of C to obtain a drawing of G with fewer crossings, a contradiction. Suppose now that v 2v 4 and v 3v 5 do not cross. By symmetry, we may assume that v 2v 4 cross vv 3 . The paths v 1v 4 and v 3v 5 cross. It must be through C so v 1 v 4 and v 3 v 5 are both edges. See Figure 5.4(C). By the Assertion, v 1 v 3 , v 3 v 4 and

Fig. 6 . 1 .

 61 Fig. 6.1. The graph K 7 and a set of edges (in bold) whose removal yields a planar graph.

  be planar after removing at most |F | edges. Hence the following Euler's formula holds:

R.ERMAN, F.HAVET, B. LIDICKY AND O. PANGRAC

Acknowledgement. We would like to thank Zdeněk Dvořák, Jiří Fiala, Daniel Král' and Riste Škrekovski for interesting questions and fruitful discussions.

* This work was partially supported by a PICS CNRS and the Hubert Curien programme Proteus 20232TC. -BLAN-0159. Partially supported by the grants GAUK 60310 and GA ČR 201/09/0197.

Similarly to the chromatic number, one may seek for bounds on the choose number of a graph with few crossings or with independent crossings.

Thomassen [START_REF] Thomassen | Every planar graph is 5-choosable[END_REF] showed that every planar graph is 5-choosable. In fact, he proved a stronger result. Definition 6.7. An inner triangulation is a plane graph such that every inner face of G is bounded by a triangle and its outer face by a cycle F = (v 1 v 2 . . . v k v 1 ).

A list assignment L of an inner triangulation G is suitable if -|L(v 1 )| = 1 and |L(v

Theorem 6.8 (Thomassen [16]). If L is a suitable list assignment of an inner triangulation G, then G is L-colourable. Theorem 6.9. Every graph with crossing number 1 is 5-choosable.

Proof. Let G be a graph with crossing number 1. Consider a plane embedding of G with one crossing C = {x 1 y 1 , x 2 y 2 }. Without loss of generality, we may assume that C is in the outer face. Free to add edges, we may assume that the outer face is bounded by the 4-cycle x 1 x 2 y 1 y 2 x 1 and that G \ C is an inner triangulation.

Let L be a 5-list assignment of G. Set c 1 ∈ L(x 1 ) and c 2 ∈ L(x 2 ) \ {c 1 }. Let L be the list assignment defined by

Problem 6.10. Is every graph with crossing number 2 five-choosable? 6.4. Graphs with small clique number or large girth. The celebrated Grötzsch Theorem [START_REF] Grötzsch | Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF] asserts that triangle-free (i.e. with clique number at most 2) planar graphs are 3-colourable. (See also [START_REF] Thomassen | A short list colour proof of Grötzsch's theorem[END_REF] for a short and elegant proof.) Together with Theorem 1.4, this suggests that the upper bounds on the chromatic number of graphs which are almost planar (they have few crossings or pairwise nondependent crossings or contain few edges whose deletion makes them planar) may be lowered when considering graphs with small clique number. We now prove a result analogous to Theorem 1.5 for K 4 -free graphs. Theorem 6.11. If a K 4 -free graph has a drawing in the plane in which no two crossings are dependent, then it is 4-colourable.

Proof. Consider a drawing of a K 4 -free graph G in which no two crossings are dependent. Let C i = {u i v i , x i y i }, i ∈ I, be the crossings. Since G is K 4 -free, without loss of generality, we may assume that u i x i is not an edge for all i ∈ I. Let G be the graph obtained from G by identifying u i with x i for every i ∈ I into a vertex z i . The graph G is planar. Thus, by the Four Colour Theorem, G admits a proper 4-colouring c . Let us define c by c(

Since, for every i ∈ I, x i and u i are not adjacent, c is a proper 4-colouring of G.

Note that Theorem 6.11 is tight because there exist K 4 -free planar graphs which are not 3-colourable. But can it be improved for triangle-free graphs or is there a triangle-free graph which has a drawing in the plane in which no two crossings are dependent and which is not 3-colourable?

For triangle-free graphs, one can show an analogue to Theorem 1.6.

Theorem 6.12. If a triangle-free graph contains a set of (at most) four edges whose deletion results in a planar graph, then it is 4-choosable.

Proof. By induction on the number n of vertices of the triangle-free graph G, the result holding trivially when n ≤ 4. A triangle-free planar graph on n vertices has at most 2n -4 edges. Hence G has at most 2n edges. Thus either G has a vertex v of degree at most three or it is 4-regular.

In the first case, by the induction hypothesis ch(Gv) = 4. Let L be a 4-listassignment of V (G). The graph Gv admits an L-colouring c that can be extended to G by assigning to v a colour in its list not assigned to any of its neighbours. So G is 4-choosable.

In the second case, since G is triangle-free it contains no K 5 and thus by Brooks' Theorem for list-colouring, ch(G) ≤ 4.

For C 3 and K 4 and more generally, for any graph or any family of graphs F, one can ask the following questions. Problem 6.13. What is the smallest integer f F (k) (resp. g F (k)) such that every F-free graph G and crossing number at most k is f F (k)-colourable (resp. g F (k)choosable)?

In particular, for C g = {C i |i = 3, . . . , g -1} the family of cycles of length less than g, the C g -free graphs are graphs with girth at least g.

. Erdös [START_REF] Erdős | Graph theory and probability[END_REF] showed that there are graphs with arbitrarily large girth and chromatic number. Hence for any fixed g, f g (k) tends to infinity when k tends to infinity. The Grötzsch graph is triangle-free, has crossing number at most 5 and chromatic number 4, so f 3 (5) ≥ 4. Thomas and Walls [START_REF] Thomas | Walls: Three-coloring Klein bottle graphs of girth five[END_REF] proved that every graph of girth at least five which admits an embedding in the Klein bottle is 3-colourable. Since every graph with crossing number at most 2 is embeddable in the Klein bottle, it follows that every graph of girth at least 5 and crossing number at most 2 is 3-colourable.

Jensen and Royle [START_REF] Jensen | Small Graphs with chromatic number 5: A computer search[END_REF] showed a K 4 -free graph with crossing number at most 6 and chromatic number 5, so f K4 (6) ≥ 5.

One can prove an analogue to Theorem 1.5 for graphs of large girth. Proposition 6.14. Let G be a graph having a drawing in the plane in which no two crossings are dependent.

(i) If G has girth at least 5, then G is 4-choosable.

(ii) If G has girth at least 10, then G is 3-choosable.

Proof. Let us prove that G is has a vertex of degree at most 3 (resp. at most 2) if G has girth at least 5 (resp. 10). Then an easy induction would give the result.

Let n be the number of vertices of G. Since no two crossings are dependent, then G has at most n/4 crossings. Hence there is a set F of at most n/4 edges such that G \ F is planar. Moreover, G \ F has girth at least 5 (resp. 10), so G \ F has fewer than 10 6 n (resp. 3 4 n) edges. Hence G has fewer than 23 12 n (resp. n) edges. Hence G has a vertex of degree at most 3 (resp. 2).


Frédéric Havet
email: frederic.havet@sophia.inria.fr

Stanislav Jendrol' ‡
email: stanislav.jendrol@upjs.sk

Roman Soták
email: roman.sotak@upjs.sk

Erika Škrabul'áková
email: erika.skrabulakova]@upjs.sk

Facial non-repetitive edge-colouring of plane graphs

A sequence r1, r2, . . . , r2n such that ri = rn+i for all 1 ≤ i ≤ n, is called a repetition. A sequence S is called non-repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are coloured. A trail is called non-repetitive if the sequence of colours of its edges is non-repetitive. If G is a plane graph, a facial nonrepetitive edge-colouring of G is an edge-colouring such that any facial trail (i.e. trail of consecutive edges on the boundary walk of a face) is nonrepetitive. We denote π ′ f (G) the minimum number of colours of a facial non-repetitive edge-colouring of G. In this paper, we show that π ′ f (G) ≤ 8 for any plane graph G. We also get better upper bounds for π ′ f (G) in the cases when G is a tree, a plane triangulation, a simple 3-connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight.

Introduction

A sequence r 1 , r 2 , . . . , r 2n such that r i = r n+i for all 1 ≤ i ≤ n, is called a repetition. A sequence S is called non-repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. The celebrated Thue Theorem [START_REF] Thue | Über unendliche Zeichenreichen, Norske Vid. Selsk[END_REF] states that arbitrarily long non-repetitive sequences can be formed using only three symbols. Alon et al. [START_REF] Alon | Non-repetitive colourings of graphs[END_REF] introduced a natural generalization of Thue's sequences for edge-colouring of graphs. An edge-colouring ϕ of a graph G is non-repetitive if the sequence of colours on any path in G is non-repetitive. The Thue chromatic index of G, denoted π ′ (G), is the minimum number of colours of a non-repetitive edge-colouring of G. Thue's sequences show that the Thue chromatic index of a path is at most 3. Actually, π ′ (P n ) = 3, for all n ≥ 5, as it is easy to see that any sequence of length 4 on two symbols contains a repetition. An immediate corollary is that the Thue chromatic index of a cycle is at most 4. In [START_REF] Currie | There are ternary circular square-free words of length n for n ≥ 18[END_REF], Currie showed that π ′ (C n ) = 4 only for n ∈ {5, 7, 9, 10, 14, 17}. For other values of n > 5, π ′ (C n ) = 3. Note that every non-repetitive edge-colouring is a proper edge-colouring. So for simple graphs π ′ (G) ≥ χ ′ (G) ≥ ∆(G). Alon et al. [START_REF] Alon | Non-repetitive colourings of graphs[END_REF] showed that π ′ (G) ≤ c∆(G) 2 for some absolute constant c and conjecture that π ′ (G) ≤ c ′ ∆(G) for some absolute constant c ′ . They proved this conjecture for several classes of graphs: the complete graph K n on n vertices satisfies π ′ (K n ) ≤ 2n and for any tree T , π ′ (T ) ≤ 4(∆(T ) -1).

In this paper, we study a variant of non-repetitive edge-colouring for plane graphs which is less constrained. We use the standard terminology according to Bondy and Murty [START_REF] Bondy | Graph Theory[END_REF] except for few notations defined throughout this article. However we recall some frequently used terms.

Let G be a plane graph. A facial trail in G is a trail made of consecutive edges of the boundary walk of some face. A facial non-repetitive edge-colouring of G is an edge-colouring of G such that any facial trail is non-repetitive. The facial Thue chromatic index of G, denoted π ′ f (G), is the minimum number of colours of a facial non-repetitive edge-colouring of G. Note that the facial Thue chromatic index depends on the embedding of the graph. For example, the graph depicted in Figure 1 has different facial Thue chromatic index depending on its embedding. With the embedding on the left, its facial Thue chromatic index is at least 4 as one of its face is a 5-cycle and with the embedding on the right its facial Thue chromatic index is 3 as shown by the depicted facial non-repetitive edge 3-colouring. Note in addition that in general a facial non- In the following, all the graphs we will consider come along with an embedding in the plane. The (geometric) dual of the plane graph G = (V, E, F ) is the graph G * = (V * , E * , F * ) with the following property: for each face α of G there is a vertex α * of G * ; two vertices α * and β * are joined by an edge e * of G * if and only if they are incident to the same edge e in G. The edge e * of G * is associated with the edge e in G and more generally the set of edges X ⊆ E(G) is associated with X * = {e * : e ∈ X}. It is well known that the dual of G * is G and that G * is also a plane graph.

Let G be a 2-edge-connected plane graph. Then its dual G * is loopless. So a proper edge-colouring of G * exists. Let a proper edge-colouring of G * be given, then assigning to each edge e of G the colour of its corresponding edge in G * produces a facial non-repetitive edge-colouring of G. Hence the facial Thue chromatic index of G is at most the chromatic index of its dual.

Proposition 1. Let G be a 2-edge-connected plane graph. Then π ′ f (G) ≤ χ ′ (G * ).
All the upper bounds on χ ′ (G * ) applies to π ′ f (G). Shannon's Theorem [START_REF] Shannon | A theorem on colouring lines of a network[END_REF]

implies π ′ f (G) ≤ 3 2 ∆(G *
) and Vizing-Gupta Theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF][START_REF] Gupta | The chromatic index and the degree of a graph[END_REF] implies that

π ′ f (G) ≤ ∆(G * )+µ(G * )
where µ(G * ) is the maximum of the edges multiplicities in G * . For some special classes of 2-edge-connected plane graphs χ ′ (G * ) = π ′ f (G). This is in particular the case for plane triangulations.

Corollary 2. Let G be a plane triangulation. Then π ′ f (G) = 3. Proof. As G is a triangulation, its dual G * is a 2-connected cubic plane graph. As shown by Tait in 1880 (see [START_REF] Tait | Note on the Theorem in geometry of position[END_REF][START_REF] Wilson | Graphs, colourings and the four-colour theorem[END_REF]) the 3-edge-colourability of such graphs is equivalent to the Four Colour Theorem ( [START_REF] Robertson | The four-color theorem[END_REF][START_REF] Wilson | Graphs, colourings and the four-colour theorem[END_REF]). Hence, by Proposition 1,

π ′ f (G) ≤ χ ′ (G * ) ≤ 3.
Now every face of G is a triangle and requires at least 3 colours in a facial non-repetitive edge-colouring. So π ′ f (G) = 3. However the chromatic index of a general (plane) graph G * is not bounded as it is at least its maximum degree ∆(G * ). In the Section 4, we show that the facial Thue chromatic index of a plane graph is bounded by 8. We get tight upper bounds for trees (Section 3), simple 3-connected graphs and Halin graphs (Section 4). In the Section 5, we improve this upper bounds when G is hamiltonian and thus derive bounds for outerplanar graphs. In the final Section 6 we discuss our results and formulate an open problem.

Lemmas on Thue sequences

To be able to prove the theorems below we need some preliminary lemmas.

For a sequence of symbols S = a 1 , a 2 , . . . , a n with a i ∈ A, for all 1 ≤ k ≤ l ≤ n, we denote by S k,l the block a k , a k+1 , . . . , a l .

Lemma 3. Let A = a 1 , a 2 , . . . , a m be a non-repetitive sequence with a i ∈ A for all i = 1, 2, . . . , m. Let B i = b i 1 , b i 2 , . . . , b i mi , 0 ≤ i ≤ r + 1 be non-repetetive se- quences with b i j ∈ B for all i = 0, 1, . . . , r + 1 and j = 1, 2, . . . , m i . If A ∩ B = ∅ then S = B 0 , A 1,n1 , B 1 , A n1+1,n2 , . . . , B r , A nr +1,m , B r+1 is a non-repetitive se- quence.
Proof. Suppose by way of contradiction that R = r 1 , . . . , r 2t is a repetitive block of S, i.e. r k = r k+t for every k = 1, 2, . . . , t. R could be a subsequence neither of the sequence A nor of any sequence B i because they are non-repetitive. Hence R consists of some blocks from A and some blocks from several consecutive B i 's, i ∈ {0, 1, . . . , r +1} too. If we delete from R all blocks of B i , i ∈ {0, 1, . . . , r +1}, then the obtained sequence R ′ is repetitive. This implies that A is repetitive, which is a contradiction.

The second lemma is an immediate implication of the existence of Thue sequences.

Lemma 4. Every cycle admits a non-repetitive edge-colouring in {1, 2, 3, 4} such that exactly one edge is coloured 4.

Proof. Let C be a cycle. Colour an edge e of C with 4. C \ e is a path and can be non-repetitively edge-coloured with {1, 2, 3} using a Thue sequence. It is easy to see that such an edge-colouring of C is non-repetitive.

Trees

An internal vertex of a tree is a vertex, that is not a leaf. An almost even tree is a tree where every internal vertex, except at most one, is of even degree. An edge incident with a leaf is called pending edge. Note that in a tree any facial trail is in fact a facial path. Lemma 5. Let S be a subdivision of a graph K 1,3 . Then π ′ f (S) = 3. Proof. In [START_REF] Breštar | Non-repetitive colorings of trees[END_REF] Breštar et al. showed that if a tree T admits a non-repetitive 3edge-colouring, then there exists a non-repetitive 3-edge-colouring of the tree T ′ obtained from T by subdividing each edge with 12 vertices. Using the above fact recursively on K 1,3 , we obtain that, for each subdivision S of K 1,3 , π ′ (S) = 3 and consequently π ′ f (S) = 3. Theorem 6. Let T be an almost even tree. Then π ′ f (T ) ≤ 3. Proof. We prove the result by induction on the number of leaves of T .

If T has two leaves then it is a path. Thus, the statement follows from the existence of arbitrary long non-repetitive sequence over three symbols (see [START_REF] Thue | Über unendliche Zeichenreichen, Norske Vid. Selsk[END_REF]). If T has three leaves, then it is a subdivision of K 1,3 and by Lemma 5 we are done.

Suppose now that T has more than three leaves. Let R be the smallest subtree of T containing all the vertices of degree at least 3 in T . Then all the leaves of R have degree at least 3 in T . Moreover, because T is almost even, there is a leaf

v of R such that deg T (v) ≥ 4. Now T -v is a forest of deg T (v)
trees among which at most one is not a path.

If deg T (v) ≥ 5, let P 0 , P 1 , P 2 and P 3 be four paths of Tv which are consecutive in the clockwise order around v. Let T 1 be the tree obtained from T by extending each of the four P i into a path Q i of length equal to the maximal length of the P j , 1 ≤ j ≤ 4. Clearly, T 1 is a supertree of T having the same number of leaves. Let T 2 be the tree obtained from T 1 by removing Q 1 and Q 2 . Then T 2 has two leaves less than T 1 and T . So, by the induction hypothesis, it admits a facial non-repetitive 3-edge-colouring. Colouring the edges of P 1 (resp. P 2 ) with the same pattern as the edges of P 3 (resp. P 0 ), we obtain a facial non-repetitive 3-edge-colouring of T .

If deg T (v) = 4, the proof is very similar to the one when deg T (v) ≥ 5. We consider three paths P 1 , P 2 and P 3 of Tv which are consecutive in the clockwise order around v. Then P 0 is the path of T whose union with v and P 1 forms a maximal facial path of T . The rest of the proof is then identical.

Theorem 7. Let T be a tree and let K be a subtree of T which is almost even. Then there exists a facial non-repetitive 4-edge-colouring of T that uses only 3 colours on the edges of K.

Proof. We proceed by induction on the number of internal vertices of odd degree in the tree T .

If there are less than two such vertices then T is almost even tree and we are done by Theorem 6.

Suppose now that T has at least two internal odd degree vertices. Consider a maximal (with respect to inclusion) almost even subtree S of T , which contains the tree K as a subgraph. The maximality of S implies that for every vertex v ∈ V (S), deg S (v) ≥ deg T (v)-1 and that the leaves of S are also the leaves of T . In addition, exactly one internal vertex with odd degree in T has all its incident edges in S. By Theorem 6, there exists a facial non-repetitive edge-colouring ϕ of S that uses colours from the set {1, 2, 3}.

Let W be the boundary walk of the unique face of T beginning and finishing in the same fixed leaf of the tree S. Let e 1 , e 2 , . . . , e k be the edges of E(T )\E(S) having one endvertex in V (S), the indices being taken in the order of appearance on W . (Clearly k is the number of internal odd degree vertices of S minus 1.) By maximality of S, those edges are pairwise disjoint. For 1 ≤ i ≤ k, let T i be the tree of T \ e i not intersecting S. Each edge e i appears twice in W . Let us denote e i,1 and e i,2 (resp. e i,3 and e i,4 ) the edges preceding and succeeding the first (resp. second) appearance of e i along W . Clearly e i,1 and e i,4 are in E(S) while e i,2 and e i,3 are not. Note that if the endvertex of e i which is not in V (S) has degree at most 2, then e i,2 = e i,3 . Moreover if e i is a pending edge then e i = e i,2 = e i,3 (in this case T i consists of one vertex only).

Let us now extend the colouring ϕ in the following way: For all 1 ≤ i ≤ k, we set ϕ(e i ) = 4. We then colour the edges of T i . Let K i be the subtree of T i induced by the edges of T i that are in a facial path containing e i in T . Then K i is either a path or a subdivision of K 1,3 and thus is almost even. Hence, by the induction hypothesis, there is a facial non-repetitive edge-colouring ϕ i of T i with colours in {1, 2, 3, 4} such that no edge of K i is assigned 4. Free to permute the colours, we may assume that ϕ i (e i,2 ) = ϕ(e i-1,4 ) and ϕ i (e i,3 ) = ϕ(e i+1,1 ) (the indices should be taken modulo k).

Let us show that the union of ϕ, ϕ 1 ,. . . ,ϕ k is a facial non-repetitive edgecolouring of T . Let P be a facial path of T . Then it contains at most two edges of {e 1 , . . . , e k }. If P has no edge in this set then it is entirely contained in either S or one of the T i 's. So it is not repetitive since ϕ 1 ,. . . ,ϕ k and ϕ are facially non-repetitive. If P contains exactly one edge in {e 1 , . . . , e k }, then this edge is the unique one of P coloured 4. Hence P is not repetitive. If P contains two edges in {e 1 , . . . , e k }, then they are consecutives: there exists 1 ≤ i < k such that edges e i and e i+1 are in E(P ). These edges are the only ones in P being coloured with 4. But since ϕ(e i,4 ) = ϕ i+1 (e i+1,2 ) and ϕ(e i,3 ) = ϕ i+1 (e i+1,1 ), P is not repetitive. Proposition 8. Let T be the tree depicted in Figure 2. Then π ′ f (T ) = 4.

e

General upper bounds

The Lemma 10 appears in [START_REF] Bondy | Graph Theory[END_REF], p. 258. For the sake of completeness we provide a simple proof of it. We need the lemma in the following formulation.

Lemma 10. Let G be a connected plane graph and T * be a spanning tree of its dual G * . Let T be a subgraph of G with edge set E(T ) associated to the edge set of

T * . Then G \ E(T ) is a tree. Proof. Clearly |E(T )| = |E(T * )| = |V (G * )| -1 = |F (G)| -1. With Euler's Formula (|E(G)|+ 2 = |V (G)|+ |F (G)|) it implies |E(G)|-|E(T )| = |V (G)|-1. It is enough to show that G \ E(T ) is connected. If not, then E(T ) contains an edge cut set which corresponds to a cycle in T * -a contradiction. Therefore G \ E(T ) is connected on |V (G)| -1 edges and thus G \ E(T ) is a tree, see [3].
Theorem 11. Let G be a connected plane graph. Then π ′ f (G) ≤ 8. Proof. Denote by T * a spanning tree of G * . Let T be the subgraph of G induced by the edges associated to the edges of T * . By Lemma 10, G \ E(T ) = T 0 is a tree and hence there is a facial non-repetitive edge-colouring ϕ(T 0 ) using colours from {1, 2, 3, 4}.

Let us colour the edges of E(T ) with the four new colors {5, 6, 7, 8}. Let us root the tree T * in some of its leaf f 0 . For every face f = f 0 of G, we denote by e f the edge shared by f and its parent in the rooted tree T * . We colour the (uncoloured) edges of the faces of G successively from the root f 0 to the leaves of T * . First, we assign to the unique uncoloured edge incident with f 0 the colour 5. Then at each step, we shall colour the uncoloured edges of a face f with colours in {5, 6, 7, 8} \ c f , where c f is a colour of the edge e f received by e f when colouring the parent of f . So far, all the coloured edges of f are those in E(T 0 ) which are coloured by ϕ except e f which is coloured with c f ∈ {5, 6, 7, 8}. Let e 1 , e 2 , . . . , e k be uncoloured edges incident with f in clokwise order around f starting at e f . (Note that no edge from the set {e 1 , e 2 , . . . , e k } is a bridge of G. Otherwise if, say, e i is a bridge then the associated edge e * i in G * is a loop. But no loop can appear in T * .) We colour the e i 's non-repetitively with three colours of {5, 6, 7, 8} \ {c f }. Doing so, no trail on the boundary of f is a repetition because the colour of e f appears only once around f and the colouring of the edges of f \ e f is non-repetitive by Lemma 3.

Theorem 12. Let G be a simple 3-connected plane graph. Then π ′ f (G) ≤ 7.

Proof. The dual graph G * of the graph G is a simple 3-connected plane graph (see [START_REF] Bondy | Graph Theory[END_REF], p. 258). By Barnette's Theorem [START_REF] Barnette | Trees in polyhedral graphs[END_REF] G * contains a spanning tree T * of maximum degree ∆(T * ) ≤ 3. To prove that there is a facial non-repetitive colouring ϕ of G with 7 colours we proceed analogously as in the proof of Theorem 11. First we colour the edges of G \ E(T ) with colours from the set {1, 2, 3, 4} analogously to the proof of Theorem 7. After the colouring ϕ, each face has all its edges coloured except at most three. To colour the remaining edges of T it is sufficient to use three new colours from {5, 6, 7} in the same way as in the proof of Theorem 11. The details are left to the reader.

Motivated by the proof of Theorem 12 one can prove the following Theorem 13. Let G be a connected plane graph and let its dual contains a Hamilton path H * . Then π ′ f (G) ≤ 6. Proof. To prove that there is a facial non-repetitive colouring ϕ of G with 6 colours we proceed analogously as in the proof of Theorem 11. First we colour the edges of G \ E(H) with colours from the set {1, 2, 3, 4} non-repetitively as in the proof of Theorem 7. Here E(H) is the set of edges corresponding to those of H * in G * . After this colouring, each face has all its edges coloured except at most two. To colour the remaining edges of H it is sufficient to use two new colours 5 and 6 in the same way as in the proof of Theorem 11. The details are left to the reader.

A Halin graph is a plane graph which is an union of a tree T of order p ≥ 3 having no vertices of degree 2 and a cycle C connecting the leaves of T in a cyclic order determining by a plane embedding of T . It is easy to see that the dual of any Halin graph contains a Hamilton path. Applying Theorem 13 we get the following. Corollary 14. Let G be a Halin graph. Then π ′ f (G) ≤ 6.

Plane hamiltonian graphs

A Hamilton cycle in a graph G is a cycle containing all the vertices. A graph G containing a Hamilton cycle is said to be hamiltonian. The aim of this section is to give better upper bounds on the facial Thue chromatic index of plane graph, provided that it is hamiltonian. Let G be a plane hamiltonian graph and H a Hamilton cycle in G. We denote by G 1 (resp. G 2 ) the subgraph of G induced by H and the edges of G inside (resp. outside) of H. Evidently G i , i = 1, 2, is a 2-connected outerplanar graph. Recall that a plane graph is outerplanar if all its vertices are incident to the outer face.

The weak dual G w of a planar graph G is the graph obtained from G * by deleting the vertex corresponding to the outer face of G (and all the edges incident with it). Fleischner et al. [START_REF] Fleischner | Outerplanar graphs and weak duals[END_REF] showed that if G is outerplanar then G w is a forest and that it is a tree if G is 2-connected. For i = 1, 2, we denote T i the weak dual of G i . The edges of G i not on H are called chords.

Discussion

In this paper, we gave upper bounds for the facial Thue chromatic index of various classes of plane graphs. However most of these upper bounds are certainly not tight. Hence, for each of these classes C, it would be nice to find its facial Thue chromatic index π ′ f (C) = max{π ′ f (G), G ∈ C} especially for the class P of plane graphs. There are many generalisations of non-repetitive sequences and for most of them it also make sense to study their graph theoretical variants. In principle, any property of sequences can be translated into a property of graphs, via coloured trails. In particular, one may take any avoidable pattern (see [START_REF] Currie | Pattern avoidance: themes and variations[END_REF]) and study its behaviour on graphs. In another direction, one may look at vertexcolouring instead of edge-colouring. The Thue chromatic number of G, denoted π(G), is the minimum number of colours of a non-repetitive vertex-colouring of G. Several papers study non-repetitive colourings, see e.g. [START_REF] Alon | Non-repetitive colourings of graphs[END_REF][START_REF] Breštar | Non-repetitive colorings of trees[END_REF][START_REF] Currie | Open problems in pattern avoidance[END_REF][START_REF] Grytczuk | Non-repetitive colorings of infinite sets[END_REF][START_REF] Grytczuk | Thue type problems of graphs, points and numbers[END_REF][START_REF] Grytczuk | Pattern avoidance on graphs[END_REF][START_REF] Kündgen | Non-repetitive colorings of graphs of bounded tree-width[END_REF][START_REF] Rampersad | A note on non-repetitive colourings of planar graphs[END_REF]. A major conjecture in this area is due to Grytczuk [START_REF] Grytczuk | Thue type problems of graphs, points and numbers[END_REF].

Conjecture 19 (Grytczuk [11]). There exists an absolute constant k such that any planar graph has a non-repetitive vertex k-colouring.

Certainly, it is equally interesting to study the facial version of all the abovementionned variants. In particular, showing that the facial Thue chromatic number of a plane graph is bounded would be a first step towards Conjecture 19.

Figure 1 :

 1 Figure 1: Two embeddings of the same graph with different facial Thue chromatic index repetitive edge-colouring is not proper. See for example the facial non-repetitive 3-edge-colouring of the graph on the right in Figure 1.In the following, all the graphs we will consider come along with an embedding in the plane. The (geometric) dual of the plane graph G = (V, E, F ) is the graph G * = (V * , E * , F * ) with the following property: for each face α of G there is a vertex α * of G * ; two vertices α * and β * are joined by an edge e * of G * if and only if they are incident to the same edge e in G. The edge e * of G * is

Figure 2 :

 2 Figure 2: A tree with facial Thue chromatic index 4

Problem 17 .

 17 What is the value of π ′ f (P)? In other words, what is the smallest integer k such that π ′ f (G) ≤ k for all plane graphs G? We believe that the following is true Conjecture 18. Let G be a 3-connected plane graph. Then π ′ f (G) ≤ 6.

Acknowledgement

We are grateful to Igor Fabrici for his stimulating discussion concerning precise value of the facial Thue chromatic index for trees. This work was supported by the Slovak Science and Technology Assistance Agency under the contract No APVV-0007-07 and partially supported by the european project FET -Aeolus.

Theorem 15. Let G be a hamiltonian plane graph and H a Hamilton cycle of G. Then π ′ f (G) ≤ 7. Moreover, if max{∆(T 1 ), ∆(T 2 )} ≤ 4 then π ′ f (G) ≤ 6 and if max{∆(T 1 ), ∆(T 2 )} ≤ 2 then π ′ f (G) ≤ 5. Proof. Let us first colour non-repetitively the edges of H with {1, 2, 3, 4} so that exactly one edge e 0 is coloured with 4. This is possible according to Lemma 4.

Next we colour the chords of G 1 . To do so we root the tree T 1 in f 0 -the face of G 1 incident to e 0 . For every face f , let e f be the edge shared by f and its parent if f = f 0 or be e 0 if f = f 0 .

We now colour the chords of the faces of G 1 successively form the root f 0 to the leaves of T 1 . At each step, we shall colour the uncoloured chords of a face f with colours in {4, 5, 6, 7}. So far, all the coloured edges of f are those in H \{e 0 } which are coloured in {1, 2, 3} except e f which is coloured c f ∈ {4, 5, 6, 7}. Let e 1 , e 2 , . . . , e k be uncoloured chords incident to f in clokwise order around f starting at e f . We colour the e i with a non-repetitive sequence with the three colour of {4, 5, 6, 7}\{c f }. Doing so, no trail on the boundary of f is a repetition because the colour of e f appears only once around f and f \ e f is non-repetitive by Lemma 3.

We proceed analogously to colour the chords of G 2 to obtain a facial nonrepetitive edge-colouring of G.

If max{∆(T 1 ), ∆(T 2 )} is at most 4 (resp. 2), we proceed in a similar way as above. But at each step we want the face f of G 1 or G 2 in consideration to have at most 3 (resp. 1) non-coloured edges. This will guarantee that 2 colours (resp. 1 colour) are enough for a non-repetitive colouring of the uncoloured chords. So the set {4, 5, 6}, (resp. {4, 5}) is enough to colour all the chords. If |V (G)| / ∈ {5, 7, 9, 10, 14, 17} then colouring non-repetitively the outer face with {1, 2, 3} and taking f 1 to be a leaf of T 1 (or T 2 ), we have the desired property. The cases when |V (G)| ∈ {5, 7, 9, 10, 14, 17} are left to reader.

An almost identical proof in which the Hamilton cycle H is replaced by the facial walk of the outer face yields the result for 2-edge-connected outerplanar graphs in which every inner face has a chord.

The bound of Theorem 15 applies for 2-connected outerplanar graphs.

Theorem 16. Let G be a 2-connected outerplanar graph. Then π ′ f (G) ≤ 7. Moreover denoting by T be the weak dual of G the following hold: