Erman -Frédéric Rok

Lidický -Ondřej Havet -Bernard

Pangrác
email: pangrac@kam.mff.cuni.cz

Rok Erman
email: rok.erman@gmail.com

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

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

Ondřej Pangrác

AUTOMATIQUE 5-colouring graphs with 4 crossings

Keywords: colouring, crossing, planar graphs, critical graphs coloration, croisement, graphe planaire, graphe critique 5-colouring graphs with 4 crossings

We disprove a conjecture of Oporowski and Zhao stating that every graph with crossing number at most 5 and clique number at most 5 is 5-colourable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colourable. We also show some colourability results on graphs that can be made planar by removing few edges. In particular, we show that if there exists three edges whose removal leaves the graph planar then it is 5-colourable.

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 is bounded in terms of its crossing number. To answer it, the concept of crossing cover is crucial. A crossing cover 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 f (k + 1) ≤ f (k) + 1. Settling a conjecture of Albertson [START_REF] Albertson | Chromatic Number, Independence Ratio, and Crossing Number[END_REF], Schaefer [13] showed that f (k) = O k 1/4 . This upper bound is tight up to a constant factor since χ(K n ) and cr

(K n ) ≤ |E(Kn)| 2 = ( n 2 ) 2 ≤ 1 8 n 4 .
Only few exact values on f (k) are known. 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 | Colouring 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.

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 | Colouring graphs with crossing[END_REF] proved that K 6 is the unique 6-critical graph with crossing number 3.

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

Oporowski and Zhao [START_REF] Oporowski | Colouring graphs with crossing[END_REF] asked whether the conclusion remains true even if cr(G) ∈ {4, 5}.

Problem 2 (Oporowski and Zhao [START_REF] Oporowski | Colouring graphs with crossing[END_REF]). If cr(G) ≤ 5 and ω(G) ≤ 5, is G 5-colourable?

We show that the answer is no as there exists a counterexample. The help of Zdeněk Dvořák was greatly appreciated while obtaining this result. Theorem 3. There exists a graph G such that cr(G) = 5, ω(G) ≤ 5 and χ(G) = 6.

On the other hand we answer in the affirmative way when cr(G) = 4. A key notion in the proof of Theorem 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 | Colouring plane graphs with independent crossings[END_REF] showed the following.

Theorem 5 (Král' and Stacho [11]). 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 23). 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, generalizing Theorem 1, we show that K 6 is essentially the unique obstruction for such a graph to be 5-colourable. Theorem 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.

Preliminaries

Drawings of graphs

A drawing G (in the plane or the sphere) of a graph G = (V, E) consists of a bijection from 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 the 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 with no crossing. An easy consequence of Euler's Formula is the following well known proposition.

Proposition 7. If G is planar then |E(G)| ≤ 3|V (G)| -6.

INRIA

A drawing of G is optimal if it minimizes the number of crossings. Note that two edges may intersect several times, either in 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 8. Let G be a graph. If cr(G) ≤ k then G has a nice drawing with at most k crossings.

Proof. Consider a drawing of G that minimizes the number of crossings between two 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 close 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)-potion 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 Consider a planar drawing of G \ F . It is a drawing of G such that each crossing contains an edge of F . 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 9. Let G be a graph. Assume that there is a set F of k edges such that G \ F is planar. Then there exists a nice drawing of G such that all the crossings contain at least one edge of F .

Since,we will consider only nice drawings, a crossing is uniquely defined by the two 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 regards 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 10. Free to rename the vertices, there is only one embedding of K 6 using exactly three crossings. (See Figure 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 7. 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. 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 11. 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 12. 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.

INRIA

Properties of 6-critical graphs

Let G be a graph and a drawing of it. A stable crossing cover is a set which is both stable and a crossing cover.

Lemma 13. If G has a stable crossing cover W then G is 5-colourable.

Proof. 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 14. Let G be a graph and v be a 5-vertex of G. Let u and w be two nonadjacent neighbours of v which are in a common face of Gv. If (Gv)/{v, w} is 5-colourable then so is G.

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

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 the cluster of every crossing containing an edge of C contains at least three vertices of C. Lemma 15. Let G be a 6-critical graph. In every drawing of G in the plane, there is no separating regular 3-cycle.

Proof. Suppose, by way of contradiction, that there is a regular 3-cycle C. Let G 1 be the graph induced by the vertices in C and inside C and G 2 a graph induced by the vertices in C and outside C. Since C is separating both G 1 and G 2 have less vertices than G. Hence, by 6-criticality of G, they are 5-colourings of those graphs. In addition, in both colourings, 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 16. Let G be a 6-critical graph distinct from K 6 . If G has a nice drawing with at most four crossings, 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 15, 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 15, 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 17. Let G be a 6-critical graph drawn (with crossings) in the plane. Then G has 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 agrees on {t, u, w}.

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

6-critical graphs embeddable on the torus or the Klein bottle

In the proof of Theorem 6, we use the knowledge of all 6-critical graphs embeddable on the torus which were obtained by Thomassen [START_REF] Thomassen | Five-coloring graphs on the torus[END_REF] and on the Klein bottle which were 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 18 (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 and the last one is a 6-regular graph on 11 vertices. Theorem 19 (Chenette et. al. [START_REF] Chenette | Five-coloring graphs in the Klein bottle[END_REF];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 Figure 2.

Lemma 20. Let G be a 6-critical graph embeddable on the torus different from K 6 . Then it is not possible to make G planar by removing three edges.

Proof. We know the complete list of graphs which must be checked due to Theorem 18. 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 7.

Lemma 21. Let G be a 6-critical graph embeddable on the Klein bottle different from K 6 . Then it is not possible to make G planar by removing three edges.

Proof. We know the complete list of graphs which must be checked due to Theorem 19. For all of those graphs except K 6 , H Now we need to deal with the last two graphs H 1 and H 2 , see Figure 2. Let us first examine H 1 . It contains two edge disjoint copies of K 6 without one edge. Each of this copy needs at least two edges to be removed by Proposition 7, 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 K 6 \ F is planar. Let us denote by u and v the two vertices of the only 2-cut of H 2 , see Figure 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 then there is still a (u, v)-path P using only edges of K 5 distinct from 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 7 for K 6 , at least three edges of it must be in F . Thus |F | ≥ 4.

6-critical graph of crossing number 5

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

Theorem 22. The graph G depicted in Figure 3 is 6-critical.

Proof. We show by contradiction that G is not 5-colourable. We refer the reader to Figure 3 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, 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.

G \ F is planar then G is (4 + k)-colourable.
Proof. By induction on k, the result holds when k = 0 by the Four Colour Theorem and then on the number of vertices of the graph. Suppose that the result is true for k. Let G 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 , 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 \ {c, d} 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 and f be two edges in F . Then the endvertices of these two edges induce a K 4 . Indeed suppose not. There is an endvertex u of e and an endvertex v of f which are not adjacent. Then G -{u, v} is (4

+ k)-colourable because F \ {e, f } is a set of 2k edges whose removal leaves G -{u, v} planar. So χ(G) ≤ χ(G -{u, v}) + 1 ≤ 4 + k + 1. Hence X = {u 1 , u 2 , v 1 , v 2 } induces a K 4 .
Let e 1 and e 2 be two edges of F . Consider the graph G ′ = G\{e 1 , e 2 }. In this graph the endvertices of e 1 and e 2 induce a 4-cycle C. Since the edges of C are adjacent to e 1 , they are not in F , so they cannot cross each other. Furthermore, they cannot be crossed by an edge e 3 ∈ F otherwise the endvertices of e 1 and e 3 would not induce a K 4 .

Let For i = 1, 2, let G i the graph obtained from G i by adding e 1 and e 2 . By the induction hypothesis, G i admits proper (4 + k + 1)-colourings c i . Moreover, G i X is a K 4 , so all the vertices of x get different colours. Hence, free to permute the colours, we may assume that c 1 and c 2 agree on X. Hence the union of c 1 and c 2 is a proper (4 + k + 1)-colouring of G.

G ′ 1 (resp. G ′ 2 )
Since cr(K 5 ) = 1 and cr(K 6 ) = 3, Theorem 23 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 equivalent to Theorem 6.

Theorem 24. Let G be a 6-critical graph distinct from K 6 . Then for any set F of at most three edges, G \ F is not planar.

Proof. Let us consider a nice drawing in G. By Lemma 13, G has no stable crossing cover.

If |F | ≤ 2 then the result is implied by Theorem 23. 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 2-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: W.l.o.g. 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(A). Then u is a stable crossing cover, a contradiction.

s = 2: W.l.o.g. 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(B). Hence G can be embedded on the torus, which is a contradictions with Lemma 20. s = 3: W.l.og. 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 7, |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 5-vertex different from u, v and w. By minimality of G, there exists a 5-colouring ̺ of Gx. By permuting the colours we assume that ̺(u) = 1, ̺(v) = 2 and ̺(w) = 3. Moreover, 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(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

INRIA

that the colour switch is correct even if u is in A the new colour of u is 5 and it is different from 2 and 3. Thus there must be a path between a and z of vertices coloured 1 and 5. We repeat the argument for colours 2 and 4 and we conclude that there must be 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 crossing, a contradiction.

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

Proof. Suppose not. Then w.l.o.g. 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 } is a stable crossing cover. See Figure 4(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(E). By Lemma 15, 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 4-cycle 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(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 15, 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(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 17 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(H). Since the removal of {e 1 , e 3 } does not make G planar,

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 w.l.o.g. 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

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)
Figure 4: The three black edges are covering all the crossings. p = 4: See Figure 4(J). We repeatedly use Lemma 17 which implies that the 4-cycles

INRIA 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)
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. The only 6-critical graph on six vertices is K 6 and ω(K 6 ) = 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 15.

W.l.o.g. 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 5(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 20.

If they cross (Figure 5(B)), it is possible to draw G on the Klein bottle, which contradicts Lemma 21, see Figure 5(C).

5-colouring graphs with 4 crossings

To prove Theorem 4, we prove the following equivalent theorem.

Theorem 25. 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 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 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 7,

|E| ≤ 3|V | -6 + cr(G) ≤ 3|V | -2.
Hence there are at least four vertices of degree 5.

Let v be an arbitrary 5-vertex and v i , 1 ≤ i ≤ 5 be the neighbours of v in the counterclockwise order around v. By criticality of G, 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 , 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 11, such a subdivision requires 5 crossings which contradicts the optimality of the drawing.

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 14, 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 Theorem 1, 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 10. 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 6(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

INRIA v ′ u 1 u 2 u 3 u 4 u 5 (A) v u 1 u 2 u 3 u 4 u 5 x y a b (B) v u 1 u 2 u 3 u 4 u 5 x y a b (C) v u 1 u 2 u 3 u 4 u 5 x y a b (D) v u 1 u 2 u 3 u 4 u 5 x y a b (E)
Figure 6: K 6 when identifying two neighbours of v.

(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 last edge incident to v, vv 1 , which is crossed, 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 Figure 6 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 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 7(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 15. If v 3 v 5 is crossed by another edge then the cycle vv 3 v 5 contradicts Lemma 16. Henceforth, we may assume that the two crossed edges are not consecutive, say vv 2 and vv 5 .

INRIA 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, 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 15. 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 7(B).

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 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 that both C and D induce a K 4 . Then 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.

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 crossing is created. Hence by the choice of G, the obtained graph G ∪ x 1 x 2 contains a K 6 . Since a K 6 has crossing number 3 and a(X) ≤ 3, three crossings of this K 6 are C, D and one contained in

G N (v) ∪ {v} . Thus 2 ≤ a(C) ≤ a(D).
Assume that 1 ≤ a(C) ≤ 2 and a(D) = 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 one of v 2 v 5 , v 2 v 4 or v 3 v 5 . Let u be the unique candidate of D.

INRIA

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 v 1 v 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 in common. Thus {w, v 1 } is a stable crossing cover, a contradiction to Lemma 13. So v 1 / ∈ D. By symmetry, we may assume that D is either {v 3 v 5 , v 4 u} (Figure 7(D)) or {v 3 v 5 , v 2 u} (Figure 7(E)) or {v 2 v 5 , v 3 u} (Figure 7(F)). In the second and third cases, Lemma 16 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}.

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 }. But 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 less 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 12, |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 7(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 intersect N (v). It contains no candidate u otherwise {uv} 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 8(A). Up to symmetry, the cluster of C is one of the following three sets

{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 }. ❼ 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

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 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 8(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 16, 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 . So N (v) ∪ {v} induces a K 6 , a contradiction. Hence without loss of generality we may assume that u = v 1 . See Figure 8(C).

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 15. Hence v 3 is a 5-vertex. Moreover, its two neighbours u and v are not adjacent and (Gv 3 )/{u, v} has at most two crossings. Then Theorem 23 and Lemma 14 yield a contradiction.

❼ 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 16.

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 15. So v 2 v 5 is crossed. It could 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 less crossings. See Figure 9(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)
Consider the paths v 2v 4 and v 3v 5 . If they cross, it is through C. Since C ⊂ N (v), the paths are v 2v 4 and v 3v 5 are actually edges. See Figure 9(B). But one can redraw v 2 v 5 along the edges of C to obtain a drawing of G with less 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 9(C). By the Assertion, v 1 v 3 , v 3 v 4 and v 4 v 5 are edges.

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 16, 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 9(D).

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 9(E). Now v 1 z is not an edge and hence {v 1 , z} is a stable crossing cover, contradicting Lemma 13. This completes the proof of Claim 6.

Claim 7. n = 4

Proof. By way of contradiction suppose that q = 4. Then {v} is a stable crossing cover, a contradiction.

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

6 Further research

Extending our results

Theorem 23 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 26. Let k be a positive integer. What is the maximum g(k) of the chromatic number over all the graphs for which there exists a set F of at most k edges such that G \ F is planar?

INRIA

Clearly, g(1) = g(2) = 5 by Theorem 23 and because K 5 is not planar and g(3) = 6 by Theorem 23 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 7, 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 10. Theorem 27. Let G be a graph with ω(G) ≤ 6. If there is a set F of at most 7 edges such that G \ F is planar then G is 6-colourable.

Proof. To prove this theorem, we show that K 7 is the unique 7-critical graph 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 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 7, we need to remove at least 8 edges to make it planar.

One of the first questions to answer is the following conjecture, extending both Theorem 6 and Theorem 4, is true.

Conjecture 28. If ω(G) ≤ 5 and there exists a set F of at most four edges such that G \ F is planar then χ(G) ≤ 5.

Critical graphs and colourability

It is easy to derive from Proposition 7 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 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 NP-completeness[END_REF]) and thus also for graphs embeddable on any other surface. The complexity of 4-colourability remains open.

Problem 29. Let Σ be a fixed surface. Does there exists a polynomial time algorithm for deciding if a graph embeddable on Σ is 4-colourable?

The answer to Problem 29 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. 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 30. Let k ≥ 0. What is the list of 6-critical graphs with crossing number at most k? When k ≤ 3, then 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. But are there any other?

Similarly to graphs embeddable on a fixed surface, the complexity of 4colourability problem for graphs with crossing number k is not known.

Problem 31. Let k ≥ 0. Does there exists a polynomial time algorithm for deciding if a graph with crossing number k is 4-colourable?

We do not even know if the number of 5-critical graphs with crossing number at most k is finite.

Problem 32. Let k ≥ 0. Is the number of 5-critical graphs of crossing number at most k finite?

Choosability

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 33. 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 INRIA -|L(v 1 )| = 1 and |L(v 2 )| = 2, -for every v ∈ V (F ) \ {v 1 , v 2 }, |L(v)| ≥ 3, and -for every v ∈ V (G) \ V (F ), |L(v)| ≥ 5.
Theorem 34 (Thomassen [START_REF] Thomassen | Every planar graph is 5-choosable[END_REF]). If L is a suitable list assignment of an inner triangulation G then G is L-colourable.

Theorem 35. Let G be a graph. If cr(G) = 1 then ch(G) ≤ 5.

Proof. 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 G 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 \ F 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

L ′ (x 1 ) = {c 1 }, L ′ (x 2 ) = {c 1 , c 2 }, L ′ (y i ) = L(y i ) \ {c 1 , c 2 } for i = 1, 2 and L ′ (v) = L(v) for every v ∈ V (F ) \ {x 1 , x 2 , y 1 , y 2 }.
Then L ′ is a suitable list assignment of G \ F . Hence G \ F admits a proper L ′ -colouring, which is an L-colouring of G by the definition of G ′ . Problem 36. Is every graph with crossing number 2 5-choosable?

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 elegant proof.) Together with Theorem 4, this suggests that the above upper bounds may be lessen when considering graphs with small clique number. We now prove a result analogous to Theorem 5 for K 4 -free graphs.

Theorem 37. If G is a K 4 -free graph which has a drawing in the plane in which no two crossings are dependent, then χ(G) ≤ 4.

Proof. 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 for every i ∈ I, u i x i is not an edge. 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(x i ) = c(x i ) = c ′ (z i ) for every i ∈ I and c(v) = c ′ (v) for every vertex v ∈ V (G) ∩ V (G ′ ). Since, for every i ∈ I, x i and u i are not adjacent, c is a proper 4-colouring of G.

Note that Theorem 37 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 6.

Theorem 38. Let G be a triangle-free graph. If there is a set F of (at most) 4 edges such that G \ F is planar then ch(G) ≤ 4.

Proof. By induction on the number n of vertices of 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-list-assignment of V (G). 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 graph F, one can ask the following questions.

Problem 39. 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 the family of cycles of length less than g, the C g -free graphs with large girth at least g. Set f g (k) = f Cg (k). Trivially, f g (k) ≤ f h (k) if g ≥ h. In particular since f 3 (k) = f (k), for any g ≥ 3, f g (k) ≤ O k 1/4 . 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-colouring 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 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 analogous to Theorem 5 for graphs of large girth.

Proposition 40. 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 ch(G) ≤ 4.

(ii) If G has girth at least 10, then ch(G) ≤ 3.

Proof. Let us prove that G is 3-degenerate (resp. 2-degenerate) if G has girth at least 5 (resp. 10). To do so it suffices to prove that it has a vertex of degree at most 3 (resp. at most 2).

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 less than 10 6 n (resp. 3 4 n) edges. Hence G has less than 23 12 n < 2n (resp. n). Hence G has a vertex of degree at most 3 (resp. 2).

INRIA

Theorem 4 .

 4 If cr(G) ≤ 4 and ω(G) ≤ 5 then χ(G) ≤ 5.

Figure 1 :

 1 Figure 1: Drawing of K 6 with three crossings.

INRIA |V | = 8 , 1 H 2 K 6 vuFigure 2 : 6 -

 812626 Figure 2: 6-critical graphs embeddable on the Klein bottle. The first three of them are embeddable on torus as well.

Figure 3 :

 3 Figure 3: A 6-critical graph of crossing number 5.

INRIA 4

 4 Colouring graphs whose crossings are covered by few edges Theorem 23. Let G be a graph. If there is a set F of at most 2k edges such that

  be the subgraph of G ′ induced by the vertices in C and inside (resp. outside) C. G ′ 1 = C for otherwise drawing e 1 inside C would give a planar drawing of G \ (F \ {e 2 }), contradicting the minimality of F . Similarly, G ′ 2 = C.

Figure 5 :

 5 Figure 5: The last case of Theorem 6.

2 )

 2 (B) and (C), respectively. The path ab (represented by dotted line in the figure) necessarily uses u 2 . Since colours φ(a) and φ(b) alternate on ab, this path cannot contain x nor u 3 , u 4 and u 5 . The paths a-b and avb separate x and y. There must be paths v 1x and v 1y. At least one of them must cross the path ab. But none of the four crossings is available for that, a contradiction. Let us now assume that x is adjacent to only two vertices of {u 3 , u 4 , u 5 }, say u 4 and u 5 . Then u 3 is adjacent to y. (Possibly u 4 and y are adjacent too.) The path ab must go through u 4 and then continue to u 1 or u 2 . It cannot go through u 3 or u 5 since the colours on the path alternate. See Figure 6(D) and (E). The path xy must cross ab. Hence either xy go through u 3 y and ab through u 4 u 2 or xy goes through xu 5 and ab through u 4 u 1 . In both cases, one of the paths v 1x and v 1y must cross ab. But there are no more crossings available.

Figure 7 :

 7 Figure 7: Two crossed edges.

Figure 7 (

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

Figure 8 :

 8 Figure 8: Three consecutive crossed edges.

Figure 9 :

 9 Figure 9: Three non-consecutive crossed edges.

Figure 10 :

 10 Figure 10: The graph K 7 and a set of edges (in bold) whose removal yields a planar graph.

RR n➦ 7110

INRIA

Acknowledgement

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

Supported by the Ministry of Education of the Czech Republic as project 1M0021620808. * This work was partially supported by a PICS CNRS, the Hubert Curien programme Proteus 20232TC and by the grant GACR 201/09/0197 5-coloration des graphes avec 4 croisements


Violeta A Montoya-Coronado

L Soullard

R Gaubert

Pascal Molle

Damien Tedoldi

Gislain Lipeme Kouyi

delineation with different levels of geographical data: which effects on combined sewer overflow modelling?

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

• Mimicking the network following the main roads provides a good approximation of the main branches of the network • Current results show a better estimation of total runoff volume when topography is available.

( 1 1

 1 sub-)catchment delineation with different levels of geographical data: which effects on combined sewer overflow modelling? V. A. Montoya-Coronado 1 *, L. Souillard 1 , R. Gaubert 1 , P. Molle², D. Tedoldi 1 , G. Lipeme Kouyi Univ Lyon, INSA Lyon, DEEP, EA7429, 69621 Villeurbanne, France ; 2 INRAE, Research Unit REVERSAAL, Lyon, France; * violeta-alexandra.montoya-coronado@insa-lyon.

VS Need of a decision support tool for stormwater disconnection at urban catchment scale

Hydrological and hydraulic models require a minimal description of the territory and its characteristics, notably the catchment and sub-catchment delineation [START_REF] Li | Methodology of Sub-Catchment Division Considering Land Uses and Flow Directions[END_REF] and the appropriate level of sewer network plan [START_REF] Ghosh | Effects of Spatial Resolution in Urban Hydrologic Simulations[END_REF], however, these data are not always reliable. The present study investigates the hydrological effect of different level of spatial data for catchment and sub-catchment delineation.

Methodology


Heidy Baide-Mairena

Arthur Coget

Nicolas Leboucq

Vincent Procaccio

Maud Blanluet

Pierre Meyer

Marie-Claire Malinge

Marie-Céline François-Heude

Mathis Moreno

David Geneviève

Heidy Baide-Mairena1

Arthur Coget3

Nicolas Leboucq3

Vincent Procaccio4

Maud Blanluet4

Pierre Meyer1

Marie-Claire Malinge4

Marie-Céline François-Heude1

Mathis Moreno1

David Geneviève6

Cecilia Marelli8

Agathe Roubertie1

Agathe Roubertie
email: a-roubertie@chu-montpellier.fr

Infantile-onset parkinsonism, dyskinesia, and developmental delay: do not forget polyglutamine defects!

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Infantile-onset parkinsonism, dyskinesia, and developmental delay: do not forget polyglutamine defects!

Introduction

Dentatorubral-pallidoluysian atrophy (DRPLA) (OMIM 125370) is one of the nine autosomal dominant polyglutamine (polyQ) defects, a group of clinically and genetically heterogeneous neurodegenerative diseases.1,2 DRPLA is caused by the expansion of a trinucleotide cytosine-adenineguanine (CAG) repeat in exon 5 of atrophin-1 (ATN1) gene. [START_REF] Koide | Unstable expansion of CAG repeat in hereditary dentatorubral-pallidoluysian atrophy (DRPLA)[END_REF] The CAG repeat expansion demonstrates genetic anticipation, especially when inherited through the paternal lineage and becomes pathogenic when expanded beyond 48 trinucleotide repeats. The clinical phenotype is heterogeneous, and the length of the repeat is correlated to poor prognosis: early onset, severity, functional impairment and eventually fatal outcome.1 Two main phenotypes have been described.1,2 The first phenotype (CAG repeats ≥65) presents a juvenile onset (<20 years) with progressive myoclonic epilepsy (PME) and encephalopathy.

The second phenotype (CAG repeats <65), also called the non-PME phenotype is characterized by adult-onset (≥20 years), ataxia, choreoathetosis, cognitive impairment, and psychiatric symptoms clinically mimicking Huntington's disease.1,2

In this report, we characterize the infantile-onset (<1 year of age) phenotype of the individual with the largest ATN1 CAG expansion reported up to now (98 repeats).

Patients and Methods

The individual was assessed in the pediatric neurology clinics at Montpellier University Medical Center. Legal guardians provided written informed consent for samples and data to be used in research and publication, including the videos.

CAG repeat number in the ATN1 gene was analyzed by a polymerase chain reaction with fluorescence-labeled primers as described elsewhere. [START_REF] Nagafuchi | Structure and expression of the gene responsible for the triplet repeat disorder, dentatorubral and pallidoluysian atrophy (DRPLA)[END_REF] The number of repeats was determined by capillary electrophoresis using an ABI 3130X automated DNA sequencer and the GeneMapper version 4.0 software (Applied Biosystems, Foster City, CA, USA). To assess the number of repeats, Genescan 500 ROX size standard was used (Applied Biosystems) and several samples with different DRPLA CAG allele lengths were sequenced as positive controls.

Results

The proband was a male first child, born to non-consanguineous parents of non-Asian origin (Fig. 1, individual III-1). Premature rupture of the membranes at 27 weeks of pregnancy resulted in oligohydramnios and pregnancy was closely monitored without abnormality. Birth occurred at 37 weeks of gestation by cesarean section due to delayed labor, with normal perinatal parameters (Apgar score 10/10, birth weight 2.870 kg (0.1 SD (Standard deviation)), height 47 cm (-0.4 SD), head circumference 33.5 cm (0 SD)).

From the age of 4 months the parents noticed the absence of eye contact and visual pursuit, limited motor achievements, and feeding difficulties. The general pediatrician reported severe hypotonia and global developmental delay. The individual also exhibited abnormal movements from 4 months of age (Video section S1). The individual was finally referred to the pediatric neurologist at 10 months. Growth failure was noticed (weight 6.9 kg (_3 SD) height 70 cm (-2.5 SD)) with microcephaly (head circumference of 42 cm (-3.4 SD). He had normal facial features as well as normal hands and feet. Clinical examination disclosed left plagiocephaly, axial hypotonia combined to axial dystonic postures with no head control, limited spontaneous and voluntary movements, distal rigidity, increased osteotendinous reflexes in the lower limbs without other pyramidal tract signs. Close assessment of movement disorders identified bradykinesia during most of the day interrupted by several episodes of involuntary, erratic, writhing movements of his face, arms, and legs. These dyskinetic paroxysms lasted between a few minutes to several hours, no evident trigger was identified. Most of the time these movements were fluid, but rapid jerking or slow and extended dystonic postures could occasionally appear. Reduced facial expression was abruptly interrupted by mouth opening dystonia (Video section S2). Involuntary movements disappeared during sleep. Between episodes the patient did not show another kind of movement disorder. EEG recording during the episodes of involuntary movements and in calm periods without paroxysmal movements was normal and the episodes were considered as non-epileptic dyskinesia.

A gastrostomy was performed at 14 months of age. At 15 months, the individual exhibited two episodes of febrile generalized clonic seizures, lasting less than 2 minutes, during an episode of gastroenteritis. Interictal wake and sleep EEG was normal and sodium valproate treatment was initiated. Seizures did not recur. The individual never acquired the ability to control his head, grab objects, or develop language and his motor function did not improve.

He died suddenly at the age of 17 months during a febrile illness.

The proband underwent a work-up at 10 months of age (detailed in Table 1). Brain MRI showed cerebral atrophy, mild atrophy of the brainstem and cerebellar vermis, thin corpus callosum, and bilateral and symmetrical globus pallidus T2-WI hyperintensities (Fig. 2).

Cerebrospinal fluid (CSF) neurotransmitters profile disclosed elevated neopterins, low levels of 5-hydroxyindolacetic acid (5-HIAA), and homovanillic acid (HVA) (Table 1).

Early developmental delay, severe hypotonia and high levels of neopterine raised the suspicion of Aicardi-Goutieres Syndrome (AGS); molecular resequencing gene panel involved in AGS (TREX1, RNASEH2B, RNASEH2A, RNASEH2C, SAMHD1, IFIH1, and ADAR) did not disclose pathogenic variant. CGH array did not show any segmental genomic copy number variations (CNVs Eight years after the proband's death, his father aged 42 years (Fig. 1 individual II-1) was referred to the neurologist for a 5-year history of progressively worsening ataxia, choreo-dystonic, and myoclonic involuntary movements associated to insidious impairment of executive functions and behavior (irritability, impulsiveness). Brain MRI showed cortical and pontocerebellar atrophy and white matter hyperintensities. Because of the clinical presentation, genetic testing for Huntington's disease and Huntington-like disorders was performed. Molecular analysis revealed a repeat expansion of 8 out of 61 copies of the CAG trinucleotide in the ATN1 gene and the diagnosis of DRPLA was established. Proband's stored DNA sample analysis identified a heterozygous expansion of 15 out of 98 copies of the CAG repeat, which was consistent with the diagnosis of DRPLA with a very high CAG repeat load.

Discussion

We described a child affected by a severe rapidly progressive neurological disease with early infantile onset, major developmental delay with axial hypotonia and no motor achievement, combined to a complex movement disorder characterized by dystonia-parkinsonism with episodes of oromandibular and limbs dyskinesia; the individual had acquired microcephaly, generalized febrile seizures and fatal outcome. Molecular testing following his father's diagnosis of DRPLA identified the largest ATN1 CAG expansion with a total of 98 repeats published in the literature up to now.

DRPLA have been mainly described in the Asian population, and it represents the most frequent cause of childhood-onset cerebellar ataxia in Japan.5 Neonatal or infantile DRPLA onset has only been reported in seven cases so far6-12 (Table 2) with a phenotype characterized by early developmental delay, regression of developmental milestones, and myoclonic or generalized tonico-clonic epileptic seizures, with variable age at onset and pharmaco-resistance. Abnormal movements were also common, including dystonia, chorea, myoclonus, and oral dyskinesia. The clinical presentation of our individual was mainly characterized by developmental delay with movement disorders; epilepsy was limited to two febrile seizures, but the individual was noteworthy by his very short life span compared to other cases,6-12 and this short life span is consistent with established correlation between CAG repeat load and early death1 (Table 2). Abnormal MRI findings were common to these neonatal or infantile-onset cases, especially cerebral, cerebellar, and brainstem atrophy; basal ganglia T2 hyperintensities has also been reported in infantile-onset cases6-12 as well as in late-onset cases.13 As in our case, most of the earlyonset cases inherited their expansion from their father; and unlike in our family, the individuals were referred mostly while the parental diagnosis was already established.6-12

Cerebrospinal fluid neurotransmitters profile has not been reported before in individuals with infantile-onset DRPLA. Atrophin-1 is a nuclear transcriptional corepressor which interacts with key proteins critical for neural progenitor cell survival, proliferation, and neuronal migration.14 Neuropathological findings of DRPLA include combined degeneration of the dentatorubral and pallidoluysian systems and white matter damage. Accumulation of expanded polyglutamine stretches have been demonstrated in the neuronal nuclei resulting in neuronal toxicity.15 Increased CSF neopterin levels may reflect an inflammatory response related to cellular damage occurring within the central nervous system and related to the disease process, as postulated in other trinucleotide repeat expansion diseases such as Huntington's disease and other adult-onset neurodegenerative disorders. [START_REF] Stoy | Tryptophan metabolism and oxidative stress in patients with Huntington's disease[END_REF][START_REF] Dale | Cerebrospinal fluid neopterin in paediatric neurology: a marker of active central nervous system inflammation[END_REF] Decreased levels of CSF homovanillic acid suggested secondary dopaminergic depletion, as observed in several neurological disorders especially those with degenerating process. [START_REF] Kurian | The monoamine neurotransmitter disorders: an expanding range of neurological syndromes[END_REF] The dopamine depletion profile was very concordant with the bradykinetic-dystonic phenotype of the individual. Although bradykinesia have been occasionally reported in juvenile or adultonset DRPLA cases,6,19 dystonia parkinsonism was not reported in previously published infantile-onset cases6-12 (Table 2); it is well admitted that parkinsonian signs are difficult to assess and may be underdiagnosed especially in infants.20 Given the limited number of previously reported patients with infantile-onset DRPLA,6-12 it is difficult to draw conclusions on the phenotypic spectrum of infantile ATN1-DRPLA; as the legal guardians of the reported individual did not agree to perform further genetic testing, we cannot rule out other contributing genetic causes in his complex phenotype. However, the phenotype of our patient shares many common features with previous cases, including parkinsonian features, and we suggest that DRPLA may be added to the growing list of genetic causes of infantile parkinsonism, especially in the context of developmental delay or regression; whether the spectrum of infantile DRPLA involves dopamine depletion will be highlighted by neurotransmitters' analysis in newly diagnosed cases.

Recently, a high prevalence of individuals carrying intermediate or pathological ranges of polyglutamine disease-associated alleles among the general population has been reported. [START_REF] Gardiner | Prevalence of carriers of intermediate and pathological polyglutamine disease-associated alleles among large population-based cohorts[END_REF] Trinucleotide repeat expansion analysis is not included (or covered by insurance) in the genetic workup of infantile or childhood-onset neurodegenerative movement disorders, especially in the absence of a significant familial history and the role of polyglutamine defect is probably underrecognized. [START_REF] Kurokawa | Clinical and neuroimaging review of triplet repeat diseases[END_REF] Our case highlights that polyglutamine diseases should be considered, even in infantile onset neurodegenerative diseases without family history. However, polyQ detection raised ethical issues; delineation of the spectrum of polyglutamine defects in infants and children will be necessary meanwhile novel techniques for genomewide evaluation of repeat expansions are under development and validation.23

Acknowledgments

We thank the individuals and their family for sharing video and clinical information and for their trust in our work and care. We thank Doctor Lagavulin for his helpful discussions.

Funding Information

None.

Author Contributions

Arthur Coget, Nicolas Leboucq, Maud Blanluet, Pierre Meyer, Marie-Claire Malinge, Marie-Céline François-Heude, Mathis Moreno, David Geneviève, Cecilia Marelli, analysis and editing of final version of the manuscript. Vincent Procaccio analysis, writing, editing of final version of the manuscript. Heidy Baide-Mairena: analysis, writing the first draft, editing of final version of the manuscript. Agathe Roubertie: design, analysis, writing, editing of final version of the manuscript.

Conflict of Interest

Authors have no conflict of interest to declare.