Omid Amini

Nicolas Bousquet

Wouter Cames Van Batenburg

Jérémie Chalopin

Ilkyoo Choi

Zdeněk Dvořák

Daniel Gonçalves

Ararat Harutyunyan

Jan Van Den Heuvel

Rémi De Joannis De Verclos

Gwenaël Joret

Feri Kardoš

Dan Král'

Andrew King

Arnaud Labourel

Tien-Nam Le

Laetitia Lemoine

Zhentao Li

Frédéric Maffray

Giuseppe Mazzuoccolo

Mickaël Montassier

Grégory Morel

Tobias Müller

Serguey Norin

Pascal Ochem

Patrice Ossona De Mendez

Matěj Stehlík

Petr Škoda

Riste Škrekovski

Michael Tarsi

Thomassé (and of course many thanks also to the coauthors that are unfortunately not mentioned in this thesis because the topic of our joint work did not really fit with the

Résumé en français

Ce manuscrit décrit une partie de mes recherches effectuées de 2009 à 2017 au sein laboratoire G-SCOP, à Grenoble, en tant que Chargé de Recherche CNRS.

Après une courte introduction à la théorie des graphes servant essentiellement à préciser la notation utilisée dans les chapitres ultérieurs, le manuscrit proprement dit commence par un long chapitre sur la coloration de graphes (Chapitre 2). On s'intéresse en particulier à des classes de graphes ayant des propriétés structurelles héritées de contraintes topologiques ou géométriques (comme les graphes plongés sur des surfaces, ou les graphes d'intersection d'objets dans le plan). Le premier problème considéré concerne la coloration à distance 2 (i.e. lorsque des sommets à distance 2 doivent recevoir des couleurs distinctes). Pour les graphes planaires, ce problème est lié à coloration d'objets du plan, qui est elle-même liée à des problèmes de transversaux de cycles dans les graphes planaires dirigés. On s'intéresse ensuite à un problème un peu plus général, où les sommets à distance exactement d, pour un entier pair d fixé, ont des couleurs distinctes.

Le second problème considéré concerne la coloration dite "impropre" des graphes. Il s'agit en fait de deux relaxations distinctes de la coloration propre classique. Dans la première variante, on demande que chaque classe de couleur soit composée de petites composantes, tandis que dans la seconde variante, on demande seulement que chaque sommet ait peu de voisins qui partagent sa couleur. On s'intéresse en particulier aux cas où ces relaxations permettent d'économiser un nombre important de couleurs en comparaison avec la coloration propre classique.

Le chapitre sur la coloration se clôt avec deux résultats liés à la coloration, et ayant aussi des liens avec les graphes plongés (ou au moins avec les graphes peu denses).

Une formulation équivalente du Théorème des 4 couleurs (qui dit que tout graphe planaire a une coloration propre avec au plus 4 couleurs), est que tout graphe cubique planaire sans isthme a une couverture de ses arêtes par 3 couplages parfaits. Dans le Chapitre 3, on s'intéresse à la couverture des arêtes des graphes cubiques par des couplages parfaits dans un cadre plus général que les graphes planaires. Ce problème est lié à une conjecture de Berge et Fulkerson, et les rares résultats obtenus sont très partiels. On prouve essentiellement des résultats d'équivalence entre diverses conjectures, et des résultats de NP-complétude. On s'intéresse également au nombre de couplages parfaits dans les graphes cubiques sans isthme.

Dans les graphes planaires, les colorations propres sont en dualité avec les flots non-nuls. Dans le Chapitre 4, on s'intéresse aux flots non-nuls (et plus généralement aux orientations vérifiant certaines propriétés similaires), dans un cadre plus général vii viii R ÉSUM É que les graphes planaires. On regarde en particulier des graphes très connexes. Un des problèmes étudiés a notamment une formulation algébrique (en lien avec l'extraction de bases additives à partir de bases linéaires dans certains espaces vectoriels). On étudie également une connexion entre les flots dans les graphes cubiques et l'existence de bisections ayant des propriétés proches de celles étudiées dans la partie sur les colorations impropres. La recherche de contrexemples à une conjecture de Ban et Linial sur ce sujet nous a amené à développer des outils pour construire des snarks dont le "nombre de flot circulaire" est au moins 5, et au final à prouver des résultats de NP-complétude liés à ce problème.

Chapter 1

Introduction

Most of the terminology and notation we use in this thesis is standard and can be found in any textbook on graph theory (such as [START_REF] Bondy | Graph Theory with Applications[END_REF] or [START_REF] Diestel | Graph Theory[END_REF]).

Basic definitions

A graph is a pair G = (V (G), E(G)) of sets, such that E(G) ⊆ {{x, y}, x, y ∈ V (G)}. The elements of V (G) are called the vertices of G, whereas the elements of E(G) are called the edges of G. We usually write xy or yx instead of {x, y} when considering an edge. If e = xy is an edge of a graph G, the vertices x and y are said to be incident with or to the edge e. The two vertices incident to an edge e are called the end points, or end vertices of e. Two vertices x and y are adjacent or neighbors in a graph G if xy is an edge of G. Two edges e = f are said to be incident if they have a common end vertex.

The number of vertices in a graph G is called the order of G. All the graphs we consider in this manuscript are finite (they have finite order).

A multigraph is a pair G = (V (G), E(G)) of sets, such that E(G) is a multiset of elements of {{x, y}, x, y ∈ V (G)}. For two vertices x, y of G, the different occurrences of {x, y} (also abbreviated at xy) are considered as a set of parallel edges between x and y. An edge of the form xx is called a loop. Most of the graphs and multigraphs considered in this manuscript will be loopless. Note that a graph is a special case multigraph (where each edge has multiplicity at most one), and to mark the difference between the two we will sometimes write simple graph instead of graph.

A directed graph (or digraph, in short) is a pair G = (V (G), E(G)) of sets, such that E(G) is a multiset of (ordered) pairs of elements of V (G). An element (x, y) of E(G) is called an arc of G, and we say that x is the tail of (x, y) while y is the head of (x, y) (in other words, we think of (x, y) as being oriented from x to y and we sometimes write -→ xy instead of (x, y)). An orientation of a (multi)graph G is a digraph obtained from G by giving each edge uv of G one of the two possible orientations (i.e. (u, v) or (v, u)). Given a digraph G, the underlying undirected (multi)graph is a (multi)graph obtained from G by replacing each arc (u, v) by an edge uv.

All the definitions in the remainder of this introduction are stated for graphs for simplicity, but hold for multigraphs as well.

Relations between graphs

We say that ϕ : V (G) → V (H) is a homomorphism between two graphs G and H, if for every edge xy of G, ϕ(x)ϕ(y) is an edge of H. The existence of a homomorphism between G and H is denoted by G → H. Two graphs G and H are said to be isomorphic if there exists a bijective homomorphism between G and H.

Let G = (V, E) and G = (V , E ) be two graphs. If V ⊆ V and E ⊆ E we say that G is a subgraph of G , denoted by G ⊆ G . If G ⊆ G and G contains all the edges xy ∈ E with x, y ∈ V , we say that G is the subgraph of G induced by V , or more simply that G is an induced subgraph of G , and we denote this by

G = G [V ].
If G ⊆ G and V = V , we say that G is a spanning subgraph of G . Given a graph H, we say that a graph G is H-free if it does not contain H as an induced subgraph.

We now define basic operations on graphs. Let G be a graph and X be a subset of vertices of G. We denote by G \ X (or sometimes G -X) the graph obtained from G by removing all the vertices of X as well as the edges incident to any vertex of X. Observe that G \ X is the subgraph of G induced by V (G) \ X. If X is a single vertex x, we write G \ x instead of G \ {x}. Let F be a subset of edges of G, we denote by G \ F (or G \ f if F = {f }) the graph obtained from G by removing all the edges of F . We call these two operations the deletion of vertices and edges from G.

Given a graph G = (V, E) and a subset X of vertices of G, we denote by G/X the graph obtained from G by contracting X into a single vertex, i.e. by removing X and adding a new vertex x adjacent to all the vertices of V \ X with a neighbor in X. In the case of multigraphs, we do something slightly more specific: for each edge uv with u ∈ X and v ∈ V \ X, we add an edge between x and v in G/X. When X consists of two adjacent vertices, the operation described above is more specifically called an edge contraction.

If a graph G can be obtained from a subgraph of H by a sequence of edge contractions, we call G a minor of H, and this relation is denoted by G m H. A class of graph that is closed under taking minors is said to be minor-closed, a class of graphs closed under taking induced subgraphs is said to be hereditary, and a class of graphs closed under taking subgraphs is said to be monotone. Note that any minor-closed class is monotone and any monotone class is hereditary. Observe also that the class of all graphs is minor-closed (and therefore also monotone and hereditary). We say that a class is proper minor-closed if it is minor-closed and distinct from the class of all graphs.

A subdivision of a graph G is a graph obtained from G by replacing each edge of G by a path (on at least one edge). We say that G is a topological minor of a graph H if H contains a subdivision of G as a subgraph. Note that if a graph contains some graph H as a topological minor, it also contains H as a minor.

Degree and neighborhood

Let G be a non-empty graph and x be a vertex of G. The set of vertices adjacent to x in G is called the neighborhood of x, denoted by N G (x). The number of edges incident to x is called the degree of x in G, denoted by d G (x). For any graph G, the degree of x in G coincides with the number of neighbors of the vertex x in G (but it need not be the case for multigraphs). In both cases, if the graph G is clear from the context we omit the subscript G and write N (x) and d(x) instead of N G (x) and d G (x). If for some k, all the vertices of G have degree k, then G is said to be k-regular, or regular. A 3-regular graph is also called a cubic graph.

The value δ(G) = min{d(x), x ∈ V (G)} is called the minimum degree of G and the value ∆(G) = max{d(x), x ∈ V (G)} is called the maximum degree of G.

Let n and m be the order and the number of edges of G. The value ad(G) = v∈V (G) d(v)/n = 2m/n is called the average degree of G. The maximum average degree of G, denoted by mad(G), is the maximum of ad(H) over all subgraphs H of G.

If for some integer k, every subgraph H of G contains a vertex of degree at most k, then G is said to be k-degenerate. Observe that every graph G is mad(G)degenerate, and every k-degenerate graph has maximum average degree at most 2k.

Let G = (V, E) be a digraph. For a subset X of V , we denote by δ + G (X) the set of arcs of E leaving X, and by δ - G (X) the set of arcs of E entering X. When X contains a single vertex v, we write δ + G (v) and δ - G (v) instead of δ + G ({v}) and δ - G ({v}). The cardinality of δ + G (v) is called the out-degree of v and is denoted by d + G (v). Similarly, the cardinality of δ - G (v) is called the in-degree of v and is denoted by d - G (v).

Distance

A path P is a graph with vertex-set V = {x 1 , x 2 , . . . , x k } and edge-set E = {x 1 x 2 , x 2 x 3 , . . . , x k-1 x k }, where all the x i are distinct vertices and k 1 is an integer. We often write P = x 1 x 2 . . . x k to denote such a path, and say that P is path between x 1 and x k (resp. between x k and x 1 ), or from x 1 to x k (resp. from x k to x 1 ). The number of edges in a path is called the length of the path. A path on k vertices is denoted by P k .

The graph obtained from a path P = x 1 . . . x k by adding an edge between x 1 and x k is called a cycle of length k, also called a k-cycle, and denoted by C k . The girth of a graph G is the length of a shortest cycle contained by G. If G does not contain any cycle, we set the girth to be infinite. An edge joining two non-consecutive vertices of a cycle is called a chord. An induced cycle in a graph G is a chordless cycle of G (that is, a cycle which is an induced subgraph of G).

The distance d G (x, y) or d(x, y) of two vertices x and y in G is the length of a shortest path between x and y in G (if such a path does not exist, we set d(x, y) to be infinite).

Connectivity

Let G be a non-empty graph. If for any two vertices x and y of G, there is a path in G between x and y, then G is said to be connected. A maximal connected subgraph of G is called a connected component, or simply a component, of G. If a vertex x of G is such that G-x has more components than G, then x is said to be a cut-vertex of G.

A graph G is said to be k-connected if for some integer k 1, G has at least k + 1 vertices and the graph G-X is connected for any set X of at most k -1 vertices of G.

Given a bipartition (X, Y ) of the vertex-set of a graph G, the edge-cut, or simply cut, associated to (X, Y ) is the set of edges with one end-point in X and the other in Y . It is usually denoted by E(X, Y ), and its cardinality is denoted by e(X, Y ). We say that a graph G = (V, E) is k-edge-connected if for every non-empty subset X ⊂ V of vertices, e(X, V \ X) k. If an edge e of G is such that Ge has more components than G, then e is said to be a bridge of G. A graph with no bridge is said to be bridgeless. Note that a graph is bridgeless if and only if all its connected components are 2-edge-connected.

Trees and bipartite graphs

A graph without cycles is called a forest, and a connected forest is called a tree. A vertex of degree 1 in a tree is called a leaf. Observe that a path P = x 1 . . . x k is a tree with exactly two leaves: x 1 and x k . Sometimes we distinguish one vertex of a tree, and call it the root. In this case, we say that we consider a rooted tree.

A graph G is bipartite if its set of vertices can be partitioned into two sets V and V , such that every edge of G has one end point in V and the other one in V . Observe that forests are bipartite. A bipartite graph is said to be a complete bipartite graph if it contains all possible edges between the two sets V and V of the bipartition. The complete bipartite graph with m vertices in the first set and n vertices in the second set is denoted by K m,n . The complete bipartite graph K 1,n is usually called the star with n leaves.

Some classes of graphs

The graph with n vertices and all possible edges is called the complete graph of order n, denoted by K n .

A graph is chordal if it contains no cycle of length at least four as an induced subgraph. A clique in a graph is a set of vertices that are pairwise adjacent. For any integer k 1, a k-tree is defined inductively as being either a clique on k vertices, or obtained from a (smaller) k-tree G by adding a vertex adjacent to a clique on k vertices of G. It is easy to see that k-trees are chordal and have clique number at most k + 1. A partial k-tree is any subgraph of a k-tree. For example, the class of partial 2-trees is exactly the class of graphs which do not contain the complete graph K 4 as a minor.

A plane graph is a graph drawn in the plane in such a way that there is no crossing of edges. A planar graph is a graph that admits a drawing in the plane with this property. In this manuscript, we will also be interested in graphs that can be drawn in more general surfaces.

Graphs on surfaces

We refer the reader to the book by Mohar and Thomassen [START_REF] Mohar | Graphs on Surfaces[END_REF] for more details or any notion not defined here. A surface is a non-null compact connected 2-manifold without boundary. A surface can be orientable or non-orientable. The orientable surface S h of genus h is obtained by adding h 0 handles to the sphere; while the non-orientable surface N k of genus k is formed by adding k 1 cross-caps to the sphere. The Euler genus of a surface Σ, denoted by eg(Σ), is defined as twice its genus if Σ is orientable, and as its non-orientable genus otherwise.

A graph G is embedded in a surface Σ if the vertices of G are distinct elements of Σ and each edge uv of G is a simple curve of Σ connecting u and v (i.e. the image of the interval [0, 1] by some bijective continuous function f such that f (0) = u and f (1) = v), whose interior is disjoint from the other edges and the vertices of G. Given such an embedding, a face of G is an arcwise connected component of Σ \ G.

We say that an embedding is cellular if every face is homeomorphic to an open disk of R 2 . Euler's Formula states that if G is a graph with a cellular embedding in a surface Σ, with vertex set V , edge set E, and face set F , then

|V | -|E| + |F | = 2 -eg(Σ).
If f is a face of a graph G cellularly embedded in a surface Σ, then a boundary walk of f is a walk consisting of vertices and edges as they are encountered when walking along the whole boundary of f , starting at some vertex and following some orientation of the face. The degree of a face f , denoted d(f ), is the number of edges on a boundary walk of f . Note that some edges may be counted more than once.

Let G be a graph embedded in a surface Σ of Euler genus g > 0. A closed curve on Σ is contractible if after cutting the surface along this curve, we obtain two components, one of which is homeomorphic to an open disk of R 2 . The edge-width of G is defined as the length of a smallest non-contractible cycle of G, and the face-width of G is defined as the minimum number of points of G intersected by a non-contractible curve on the surface.

Chapter 2

Graph coloring

This chapter includes some contributions to several graph coloring problems, with an emphasis on graph classes with a topological or geometrical flavour.

We first investigate colorings of graphs in which vertices at a certain distance are required to have distinct colors. In planar graphs, when the constraint is on vertices at distance two, this is connected to coloring problems for non-overlapping regions in the plane. More general coloring problems for regions in the plane (when the regions intersect in a less restricted way) are also investigated.

We then study two variants of proper coloring for graphs embedded on surfaces. In the first variant, adjacent vertices may receive the same color, but we require that connected components of vertices with the same color are not too large. In the second variant, we only require that each vertex shares the color of few of its neighbors.

We conclude this chapter with two results related to coloring graphs on surfaces (or more generally sparse graphs).

Definitions

For some integer k 1, a proper k-coloring of the vertices of G is a map c : V (G) → {1, . . . , k} such that for every edge xy of G, c(x) = c(y). The elements from {1, . . . , k} are called colors, and the set of all vertices colored with a specific color is called a color class. Observe that a proper coloring of a graph is a partition of its set of vertices into color classes, each of which is an independent set (i.e. a set of vertices that are pairwise non-adjacent). If a graph admits a proper k-coloring, it is said to be k-colorable. The smallest k such that a graph G is k-colorable is called the chromatic number of G, denoted by χ(G). A graph with chromatic number k is said to be k-chromatic. Observe that the chromatic number of a graph G on n vertices is related to the clique number ω(G) (the maximum order of a clique in G), and the independence number α(G) (the maximum cardinality of an independent set in G) as follows: ω(G) χ(G) and χ(G) n α(G) . A list assignment L : V (G) → 2 N on the vertices of a graph is a map which assigns to each vertex v of the graph a list L(v) of prescribed integers. If for some integer t, every list has size at least t, then L is called a t-list assignment.

CHAPTER 2. GRAPH COLORING

Let L be a list assignment on the vertices of a graph G. A coloring c of the vertices of G such that for every vertex v, c(v) ∈ L(v) is called an L-coloring of G. If such a coloring exists, then G is said to be L-colorable. The list chromatic number or choice number ch(G) is the minimum value t, so that for every t-list assignment L on the vertices of G, the graph G is L-colorable. The concept of choosability was introduced by Vizing [START_REF] Vizing | Coloring the vertices of a graph in prescribed colors[END_REF], and Erdős, Rubin and Taylor [START_REF] Erdős | Choosability in graphs[END_REF]. Note that for any graph G, χ(G) ch(G). A simple greedy algorithm shows that if G is k-degenerate, then ch(G)

k + 1 (in particular, graphs with maximum degree ∆ have choice number at most ∆ + 1). This observation is particularly useful when we consider hereditary classes of graphs, i.e. classes of graphs that are closed under taking induced subgraphs. Assume that F is a hereditary class of graphs, and there is a constant c such that every graph G ∈ F on n vertices has at most cn edges. Then every graph of G contains a vertex of degree at most 2c , and since F is hereditary, it implies that any graph of F is 2c -degenerate and then ( 2c + 1)-choosable. We write it as an observation, for future reference.

Observation 2.1.1. If F is a hereditary class of graphs, and there is a constant c such that every graph G ∈ F on n vertices has at most cn edges, then any graph of F is ( 2c + 1)-choosable.

For any graph G = (V, E), we define the line graph L(G) of G to be the graph with vertex-set E, where two vertices u, v ∈ E are adjacent in L(G) if and only if the corresponding edges are incident in G.

The smallest integer k, such that the edges of a graph G can be colored with k colors in such a way that any two incident edges have distinct colors, is called the chromatic index of G, denoted by χ (G). Such a coloring is called a (proper) edge coloring of G. Note that χ (G) = χ(L(G)). A classical theorem of Vizing [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF] states that every simple graph with maximum degree ∆ has chromatic index at most ∆ + 1, and a classical result of Shannon [START_REF] Shannon | A theorem on colouring lines of a network[END_REF] states that every multigraph with maximum degree ∆ has chromatic index at most 3 2 ∆. These two results are best possible. For the latter, this is easily seen for even ∆ by taking a triangle and replacing each edge by ∆ 2 parallel edges. This example is sometimes called the fat triangle.

We also define the list chromatic index ch (G) of G as the choice number of the line graph of G. The classical list coloring conjecture states that χ (G) = ch (G) for any multigraph G (see [START_REF] Jensen | Graph Coloring Problems[END_REF] for more details about this conjecture and its origins, and [START_REF] Zs | Graph colorings with local constraints -a survey[END_REF] for a survey on list coloring).

Coloring graphs at distance two

Given a graph G = (V, E), the square of G, denoted by G 2 , is the graph with vertexset V , in which two vertices are adjacent if and only if they are at distance at most 2 in G. Note that if a graph G has maximum degree at most ∆, then G 2 has maximum degree at most ∆ 2 , and then (list) chromatic number at most ∆ 2 + 1. This bound is sharp, as shown by the 5-cycle, or the Hoffman-Singleton graph. More generally, it is not difficult to construct infinite families of graphs of (increasing) maximum degree ∆ and chromatic number of the square at least (1o(1))∆ 2 . Typical examples of such graphs are incidence graphs of finite projective planes. In these examples, we even have that the clique number of the square of the graphs is of order (1o(1))∆ 2 .

It was conjectured by Wegner in 1977 [START_REF] Wegner | Graphs with given diameter and a coloring problem[END_REF] (see also the book of Jensen and Toft [START_REF] Jensen | Graph Coloring Problems[END_REF]Section 2.18]) that the situation is quite different for planar graphs. Conjecture 2.2.1 ( [START_REF] Wegner | Graphs with given diameter and a coloring problem[END_REF]). For any planar graph G of maximum degree ∆,

χ(G 2 )    7, if ∆ = 3, ∆ + 5, if 4 ∆ 7, 3 2 ∆ + 1, if ∆ 8.
Wegner also gave examples showing that these bounds would be tight. These examples are very similar to the graph obtained from the fat triangle described in Section 2.1, by subdividing every edge once (i.e. replacing every edge by a path on 2 edges). The first upper bound on χ(G 2 ) for planar graphs in terms of ∆, χ(G 2 ) 8∆ -22, was implicit in the work of Jonas [START_REF] Jonas | Graph coloring analogues with a condition at distance two: L(2, 1)labelings and list λ-labelings[END_REF]. This bound was later improved by Wong [START_REF] Wong | Colouring graphs with respect to distance[END_REF] to χ(G 2 ) 3∆ + 5 and then by van den Heuvel and McGuinness [START_REF] Van Den Heuvel | Coloring the square of a planar graph[END_REF] to χ(G 2 ) 2∆ + 25. It was shown that χ(G 2 ) 9 5 ∆ + 1 for ∆ 750 by Agnarsson and Halldórsson [START_REF] Agnarsson | Coloring powers of planar graphs[END_REF]. Later, Molloy and Salavatipour [START_REF] Molloy | A bound on the chromatic number of the square of a planar graph[END_REF] proved that χ(G 2 ) 5 3 ∆ + 78. Havet, van den Heuvel, McDiarmid and Reed [START_REF] Havet | List colouring squares of planar graphs[END_REF] proved that the square of any K 3,k -minor free graph (for any fixed k) of maximum degree ∆ has list chromatic number at most 3 2 ∆ + o(∆). Note that for any fixed surface Σ, there is an integer k such that all the graphs embeddable on Σ are K 3,k -minor free. Therefore, the previous result holds for graphs that are embeddable on any fixed surface (and in particular, for planar graphs).

A cyclic coloring of a graph G embedded in some surface Σ is a coloring of the vertices of G such that any two vertices lying in the boundary of the same face have distinct colors. The minimum number of colors required in a cyclic coloring of an embedded graph is called the cyclic chromatic number χ * (G). This concept was introduced for plane graphs by Ore and Plummer [START_REF] Ore | Cyclic coloration of plane graphs[END_REF], who also proved that for a plane graph G we have χ * (G) 2∆ * (G), where ∆ * (G) denotes the maximum number of vertices lying on a face of G. Borodin [START_REF] Borodin | Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs[END_REF] (see also Jensen and Toft [108,page 37]) conjectured the following.

Conjecture 2.2.2 ([15]

). For any plane graph G, we have χ * (G)

3 2 ∆ * (G) .
The bound in this conjecture is again best possible: the extremal examples are very similar to the planar dual of the fat triangle described in Section 2.1. Borodin [START_REF] Borodin | Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs[END_REF] proved Conjecture 2.2.2 for ∆ * = 4. For general values of ∆ * , the original bound χ * (G) 2∆ * of Ore and Plummer [START_REF] Ore | Cyclic coloration of plane graphs[END_REF] was improved by Borodin, Sanders and Zhao [START_REF] Borodin | On cyclic colorings and their generalizations[END_REF] to χ * (G) 9 5 ∆ * and later by Sanders and Zhao [START_REF] Sanders | A new bound on the cyclic chromatic number[END_REF] to χ * (G) 5 3 ∆ * . Cyclic coloring of embedded graphs, and coloring the square of graphs, can both be seen as special cases of a more general notion, which we introduced with Amini and van den Heuvel in [START_REF] Amini | A unified approach to distance-two colouring of graphs on surfaces[END_REF]. Let G be a graph, and assume that for each vertex v of G, we are given a subset Σ(v) of neighbors of v in G. Such a function Σ is called neighborhood system of G. A Σ-coloring of G is a proper coloring of the vertices of G such that for any vertex v, all the vertices of Σ(v) have distinct colors. The minimum number of colors in a Σ-coloring of G is denoted by χ(Σ). Note that if we let ∆(Σ) denote the maximum number of vertices lying in some set Σ(v), we have χ(Σ) ∆(Σ).

If one sets Σ(v) = N (v) for each vertex v, then a Σ-coloring is precisely a coloring of G 2 , and ∆(Σ) is equal to ∆(G), the maximum degree of G. Now, assume that G is embedded in some surface Σ. Add a new vertex v f inside each face f , and connect each v f to all the vertices lying in the boundary of f . In the resulting graph G , set Σ (v f ) = N (v f ) for each newly created vertex v f , and otherwise set Σ (v) = ∅. Observe that χ(Σ ) = χ * (G) and ∆(Σ ) = ∆ * (G).

With Amini and van den Heuvel, we proved the following result [START_REF] Amini | A unified approach to distance-two colouring of graphs on surfaces[END_REF], which implies asymptotic versions of Conjectures 2.2.1 and 2.2.2 (using the connections mentioned in the previous paragraph). Theorem 2.2.3 ([6]). For any fixed surface S, any graph G embedded in S, and any neighborhood system Σ of G, we have χ(Σ) 3 2 ∆(Σ) + o(∆(Σ)). Our proof builds upon the work of Havet, van den Heuvel, McDiarmid and Reed [START_REF] Havet | List colouring squares of planar graphs[END_REF]. We first use a discharging argument to reduce our problem to that of (list) coloring the edges of multigraphs, and then use the machinery developed by Kahn [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF] while proving that the list chromatic index of a multigraph is close to its fractional counterpart. The proof of Kahn consists in repeatedly sampling matchings from probability distributions associated to interior points of the matching polytope. We will not say more about the proof here, but related ideas will be encountered in Chapter 3, where we will be sampling perfect matchings from a probability distribution associated to a specific point of the perfect matching polytope (instead of the matching polytope).

Given a graph class F, we say that F is σ-bounded if there is a function f such that for that every G ∈ F, every neighborhood system Σ for G satisfies χ(Σ) f (∆(Σ)). Let C F be the supremum of χ(Σ)/∆(Σ), over all graphs G ∈ F and non-empty neighborhood systems Σ for G. If C F < ∞, we say that F is linearly σ-bounded. Theorem 2.2.3 shows that graphs embeddable on a fixed surface are linearly σ-bounded, and thus σ-bounded. This raises the following two natural questions.

1. Which classes of graphs are σ-bounded?

Which classes of graphs are linearly σ-bounded?

For a graph G, the 1-subdivision G * of G is the graph obtained from G by subdividing every edge exactly once, i.e. by replacing every edge by a path with 2 edges. For some integer n 4, consider K * n , the 1-subdivision of K n , and for every vertex of degree two in K * n , set Σ(v) = N (v), and otherwise set Σ(v) = ∅. A Σcoloring is then exactly a proper coloring of K n , so χ(Σ) n, while ∆(Σ) = 2. Hence, the class containing the 1-subdivisions of all complete graphs is not σ-bounded.

It follows that there exist graph classes that have bounded maximum average degree (or degeneracy, or arboricity), but that are not σ-bounded.

A star coloring of a graph G is a proper coloring of the vertices of G so that every pair of color classes induces a forest of stars. The star chromatic number of G, denoted χ s (G), is the least number of colors in a star coloring of G. We say that a class F of graphs has bounded star chromatic number if the supremum of χ s (G) for all G ∈ F is finite.

With Dvořák [START_REF] Dvořák | Distance-two coloring of sparse graphs[END_REF], we proved the following precise characterisation theorem, answering the two questions above. Theorem 2.2.4 ( [START_REF] Dvořák | Distance-two coloring of sparse graphs[END_REF]). Let F be a class of graphs. The following four propositions are equivalent:

(i) F is linearly σ-bounded. (ii) F is σ-bounded. (iii)
The supremum of χ(Σ), over all G ∈ F and all neighborhood systems Σ for G with ∆(Σ) = 2, is finite. (iv) F has bounded star chromatic number.

Given a graph G = (V, E) and a neighborhood system Σ for G, a Σ-clique is a set C of elements of V such for that any pair u, v ∈ C there is a vertex w ∈ V such that u, v ∈ Σ(w). The maximum size of a Σ-clique is denoted by ω(Σ). Note we trivially have ∆(Σ) ω(Σ) χ(Σ).

In the case where Σ(v) = N (v) for every vertex v of G, the parameter ω(Σ) has been studied for several graph classes, such as planar graphs [START_REF] Hell | Largest planar graphs of diameter two and fixed maximum degree[END_REF] and linegraphs [START_REF] Chung | The maximum number of edges in 2K 2 -free graphs of bounded degree[END_REF][START_REF] Faudree | The strong chromatic index of graphs[END_REF]. As previously, it is natural to investigate classes F for which there is a function f , such that for any G ∈ F and any neighborhood system Σ for G, we have ω(Σ) f (∆(Σ)).

For a class of graphs F, we denote by F its closure, i.e. the set of all subgraphs of graphs of F. Note that if F is monotone, then F = F.

Let F be a class of graphs such that F contains 1-subdivisions of arbitrarily large cliques. Then, as observed above, ω cannot be bounded by a function of ∆ in F. With Dvořák [START_REF] Dvořák | Distance-two coloring of sparse graphs[END_REF], we proved that the converse also holds. Theorem 2.2.5 ([42]). Let F be a class of graphs. The following statements are equivalent: (i) The supremum of ω(Σ) over all graphs G ∈ F and all neighborhood systems Σ for G with ∆(Σ) = 2 is finite. (ii) There is a constant C such that every G ∈ F and every neighborhood system Σ for G satisfies ω(Σ) C • ∆(Σ). (iii) There is a function f such that every G ∈ F and every neighborhood system Σ for G satisfies ω(Σ) f (∆(Σ)).

(iv) F does not contain 1-subdivisions of arbitrarily large cliques.

It turns out that these results about the chromatic number and the clique number of neighborhood systems have some interesting connections with the recently developed theory of sparse graphs. The notion of a class of bounded expansion was introduced by Nešetřil and Ossona de Mendez in [START_REF] Nešetřil | Linear time low tree-width partitions and algorithmic consequences[END_REF][START_REF] Nešetřil | Grad and classes with bounded expansion I. Decompositions[END_REF][START_REF] Nešetřil | Grad and classes with bounded expansion II. Algorithmic aspects[END_REF][START_REF] Nešetřil | Grad and classes with bounded expansion III. Restricted graph homomorphism dualities[END_REF]. Examples of such classes include minor-closed classes, topological minor-closed classes, classes locally excluding a minor, and classes of graphs that can be drawn in a fixed surface with a bounded number of crossings per edge. It was recently proved that first-order properties can be decided in linear time in classes of bounded expansion [START_REF] Dvořák | Deciding first-order properties for sparse graphs[END_REF].

For more about this topic, the reader is referred to the survey book of Nešetřil and Ossona de Mendez [START_REF] Nešetřil | Sparsity -Graphs, Structures, and Algorithms[END_REF].

A graph H is a shallow topological minor of G at depth d if G contains a ( 2d)subdivision of H (i.e. a graph obtained from H by subdividing each edge at most 2d times) as a subgraph. For any d 0, let ∇ d (G) be defined as the maximum of Let G be a graph. For an integer d 1 and a vertex v ∈ V (G), let N d (v) denote the set of vertices at distance at most d from v in G, excluding v itself. We say that Σ is a d-neighborhood system if Σ(v) ⊆ N d (v) for all v ∈ V (G). A class of graphs F is said to be σ-bounded at depth d if there exists a function f such that for any G ∈ F and any d-neighborhood system Σ for G, we have χ(Σ) f (∆(Σ)). Note that a class is σ-bounded at depth 1 precisely if it is σ-bounded.

With Dvořák [START_REF] Dvořák | Distance-two coloring of sparse graphs[END_REF], we proved that if a class F of graphs is σ-bounded at depth d for every integer d 1, then F has bounded expansion [START_REF] Dvořák | Distance-two coloring of sparse graphs[END_REF]. However, we observed that the converse is not true. Consider the graph S n consisting of a star with n 2 + n leaves {v i,j | 1 i < j n} ∪ {v i | 1 i n}. For any i < j, set Σ(v i,j ) = {v i , v j }, and set Σ(v) = ∅ for all other vertices. Note that Σ is a 2-neighborhood system and ∆(Σ) = 2, but χ(Σ) n. Hence, the family F = {S n | n 1} is not even σ-bounded at depth 2 (while it clearly has bounded expansion).

A way to circumvent this is to add a notion of complexity to that of a neighborhood system Σ. A realizer R for a d-neighborhood system Σ is a set of paths of length at most d between all pairs u, v such that u ∈ Σ(v). Given such a realizer R, we define λ(R) as the maximum over all vertices u of G of the number of paths of R containing u. The complexity λ(G, Σ) is the minimum of λ(R) over all realizers of Σ.

If we only allow d-neighborhood systems Σ with λ(G, Σ) bounded by a fixed function of d, then it can be shown that having bounded expansion is equivalent to being σ-bounded at each depth.

Nešetřil and Ossona de Mendez [START_REF] Nešetřil | On nowhere dense graphs[END_REF] call a class F of graphs somewhere dense if there exists an integer d, such that the set of shallow topological minors at depth d of graphs of F is the set of all graphs. Otherwise F is nowhere dense.

If a graph G contains a ( 2d -1)-subdivision of a clique on k vertices, then as above we can find a d-neighborhood system Σ for G with ∆(Σ) = 2, and ω(Σ) k. This remark has the following direct consequence. If there is a function f , such that for any d 1, for any G ∈ F and for any d-neighborhood system Σ for G, we have ω(Σ) f (∆(Σ), d), then F is nowhere-dense. Again, we note that if we require that the complexity of the neighborhood systems Σ we consider is bounded by a function of the depth, the two properties are indeed equivalent.

Coloring geometric graphs 2.3.1 Jordan regions

A Jordan region is a subset of the plane that is homeomorphic to a closed disk. A family F of Jordan regions is touching if their interiors are pairwise disjoint. If any point of the plane is contained in at most k regions of F, then we say that F is k-touching. Whenever we will encounter such a collection F of geometric objects, we will implicitly consider the underlying associated intersection graph G(F), whose vertices are the elements of F and such that two vertices are adjacent if and only the two corresponding elements of F intersect. Whenever we talk about the chromatic number or the clique number of F, we indeed talk about the the chromatic number or the clique number of G(F). The chromatic number of families of geometric objects in the plane have been extensively studied since the sixties [START_REF] Asplund | On a coloring problem[END_REF][START_REF] Gyárfás | Covering and coloring problems for relatives of intervals[END_REF][START_REF] Kostochka | On upper bounds for the chromatic number of graphs[END_REF][START_REF] Kostochka | Covering and coloring polygon-circle graphs[END_REF][START_REF] Mcguinness | Coloring arcwise connected sets in the plane I[END_REF]. The reader is referred to [START_REF] Kostochka | Coloring intersection graphs of geometric figures with a given clique number[END_REF] for a survey on the chromatic and clique numbers of geometric intersection graphs.

As we have seen in the previous section, Theorem 2.2.3 implies that any plane graph with maximum face order ∆ * has a cyclic coloring with 3 2 ∆ * + o(∆ * ) colors (this is an asymptotic version of Conjecture 2.2.2). This result easily implies the following.

Theorem 2.3.1. Every k-touching family of Jordan regions can be properly colored (i.e. such that intersecting regions have distinct colors) with 3 2 k + o(k) colors. To see this, consider a k-touching family F of Jordan regions and construct a plane graph G from F as follows. For each region r ∈ F, add a new vertex x r inside the region r. Then, for any intersection point p (we can assume without loss of generality that there are only finitely many such points), and for any two regions r 1 and r 2 containing p and consecutive in the cyclic order around p, add an edge between x r 1 and x r 2 (note that the resulting graph might have multiple edges). Observe that each intersection point p corresponds to some face of G. Finally, triangulate all faces that do not correspond to intersection points. Then the maximum face order of G is precisely k, and two regions of F intersect if and only if the corresponding vertices lie on the same face (see Figure 2.1, left).

Another (perhaps simpler) way is to derive Theorem 2.3.1 directly from Theorem 2.2.3. We construct a bipartite plane graph H from F as follows: For each region r ∈ F, add a new vertex x r inside the region r and for any intersection point p, add a new vertex y p (at the same location as p). Then, for each region r and each intersection point p ∈ r, add an edge between x r and y p . Finally, we define a neighborhood system Σ for H by setting Σ(y p ) = N (y p ) for each intersection point p and Σ(x r ) = ∅ for each region r, and observe that ∆(Σ) = k and a Σ-coloring of H is exactly a coloring of F such that intersecting regions are assigned different colors (see Figure 2.1, right).

It can be checked that Theorem 2.3.1 is asymptotically best possible by considering the family obtained from the fat triangle described in Section 2.1 by thickening each edge (i.e. replacing each edge by a very thin region containing the edge). The corresponding k-touching collection of 3k 2 regions is k-touching, but any coloring of the regions requires 3k 2 colors (since any two regions intersect). This example is depicted in Figure 2.2, for k = 6.

Figure 2.2: A 6-touching family of Jordan regions requiring 9 colors

An interesting property of the example described above is that it contains pairs of regions intersecting in two points. Let us say that a k-touching collection of Jordan regions is simple if any two regions of F intersect in at most one point.

If a k-touching family of Jordan regions has the property that each region contains at most two intersection points, then each region can be thought of as an edge of some (planar) multigraph with maximum degree k. By the theorem of Shannon mentioned in Section 2.1, the regions can then be colored with 3k/2 colors. If moreover, the k-touching family is simple, then the multigraph is indeed a graph and the regions can be colored with k + 1 colors1 by the theorem of Vizing mentioned in Section 2.1. This triggered Reed and Shepherd [START_REF] Reed | The Gallai-Younger conjecture for planar graphs[END_REF] to ask the following question in 1996.

Problem 2.3.2 ([168]

). Is there a constant C such that for any simple touching family F of Jordan regions, χ(G(F)) ω(G(F)) + C? Can we take C = 1?

We answered this question by the positive with Cames van Batenburg and Müller [START_REF] Cames Van Batenburg | Coloring Jordan regions and curves[END_REF].

Theorem 2. 3.3 ([23]). For k 490, any simple k-touching family of Jordan regions is (k + 1)-colorable.

Our proof is a fairly simple discharging argument (applied to the same bipartite plane graph as the one described above in the sketch of the proof of Theorem 2.3.1). Ossona de Mendez pointed out to us later that he obtained close results in 1999 (see [START_REF] Ossona De Mendez | The Reduced Genus of a Multigraph[END_REF]). His results were stated with a different terminology, but he essentially proved that for sufficiently large k, and for any simple k-touching family F of Jordan regions, the intersection graph G(F) is (k + 1)-degenerate, and therefore (k + 2)-choosable.

Note that apart from the constant 490, Theorem 2.3.3 is best possible. With Gonçalves and Labourel [START_REF] Esperet | Coloring non-crossing strings[END_REF], we proved that every simple k-touching family of Jordan regions is 3k-colorable (our result is actually stated for k-touching families of strings, see Section 2.3.2, but it easily implies the result on Jordan regions). Together with Theorem 2.3.3, this easily implies the following corollary.

Corollary 2.3.4 ([23]

). Any simple k-touching family of Jordan regions is (k + 327)colorable.

Observe that for a given simple touching family F of Jordan regions, if we denote by k the least integer so that F is k-touching, then ω(G(F)) k, since k Jordan regions intersecting some point p of the plane are pairwise intersecting. Therefore, we obtain the following immediate corollary, which is a positive answer to the problem raised by Reed and Shepherd.

Corollary 2.3.5 ([23]). For any simple touching family

F of Jordan regions, χ(G(F)) ω(G(F)) + 327 (and χ(G(F)) ω(G(F)) + 1 if ω(G(F)) 490).
It turns out that Theorem 2.3.3 also implies a positive answer to a question raised by Hliněný in 1998 [START_REF] Hliněný | The maximal clique and colourability of curve contact graphs[END_REF]. A string is the image of some continuous injective function from [0, 1] to R 2 , and the interior of a string is the string minus its two endpoints. A contact systems of strings is a set of strings such that the interiors of any two strings have empty intersection. In other words, if c is a contact point in the interior of a string s, all the strings containing c distinct from s end at c. A contact system of strings is said to be one-sided if for any contact point c as above, all the strings ending at c leave from the same side of s (see Figure 2.4, left). Hliněný [START_REF] Hliněný | The maximal clique and colourability of curve contact graphs[END_REF] raised the following problem in 1998: Problem 2. 3.6 ([99]). Let S be a one-sided contact system of strings, such that any point of the plane is in at most k strings, and any two strings intersect in at most one point. Is it true that G(S) has chromatic number at most k + o(k)? (or even k + c, for some constant c?) The following simple corollary of Theorem 2.3.3 gives a positive answer to Problem 2.3.6.

Corollary 2.3.7 ([23]

). Let S be a one-sided contact system of strings, such that any point of the plane is in at most k strings, and any two strings intersect in at most one point. Then G(S) has chromatic number at most k + 127 (and at most k + 1 if k 490).

The idea is simply to thicken each string s in the contact system to turn s into a (very thin) Jordan region (see Figure 2.4, from left to right). The fact that the contact system is one-sided implies that each intersection point contains precisely the same elements before and after the modification. We can then apply Theorem 2.3.3.

Strings and Jordan curves

A Jordan curve is the boundary of some Jordan region of the plane. We say that a family of Jordan curves (resp. strings) is touching if for any two Jordan curves (resp. strings) a, b, the curves (resp. strings) a and b do not cross (for Jordan curves, this is equivalent to say that either the interiors of the regions bounded by a and b are disjoint, or one is contained in the other). Moreover, if any point of the plane lies on at most k Jordan curves (resp. strings), we say that the family is k-touching.

With Gonçalves and Labourel [START_REF] Esperet | Coloring non-crossing strings[END_REF], we conjectured the following.

Conjecture 2.3.8 ([53]

). There is a constant c such that any k-touching family of strings is ck-colorable.

An interesting class of strings for which Conjecture 2.3.8 was already known to hold is the class of x-monotone strings. An x-monotone string is a string such that every vertical line intersects it in at most one point. Alternatively, it can be defined as the curve of a continuous function from an interval of R to R. Sets of k-touching x-monotone strings are closely related to bar k-visibility graphs. A bar k-visibility graph is a graph whose vertex-set consists of horizontal segments in the plane (bars), and two vertices are adjacent if and only if there is a vertical segment connecting the two corresponding bars, and intersecting no more than k other bars. It is not difficult to see that the graph of any set of k-touching x-monotone strings is a spanning subgraph of some bar (k -2)-visibility graph, while any bar (k -2)-visibility graph can be represented as a set of k-touching x-monotone strings. Using this correspondence, it directly follows from [START_REF] Dean | Bar k-Visibility Graphs[END_REF] that k-touching x-monotone strings are (6k -6)-colorable, and that the complete graph on 4k -4 vertices can be represented as a set of k-touching x-monotone strings. If the left-most point of each x-monotone string intersects the vertical line x = 0, then it directly follows from [START_REF] Felsner | Parameters of Bar k-Visibility Graphs[END_REF] that the strings can be colored with 2k -1 colors (and the complete graph on 2k -1 vertices can be represented by k-touching x-monotone strings in this specific way).

With Gonçalves and Labourel [START_REF] Esperet | Coloring non-crossing strings[END_REF], we proved Conjecture 2.3.8 in the particular case where any two strings intersect a bounded number of times (in this case the constant c depends on this number). In particular we proved that if each string is a (straight-line) segment (in which case any two strings clearly intersect at most once), then the k-touching family is (k + 5)-colorable. To show this, we proved that if F is a k-touching family of n segments, then the number of edges of the corresponding intersection graph is less than 1 2 (k + 5)n. Since the class of such intersection graphs is hereditary, it follows from Observation 2.1.1 that such graphs are (k + 5)-colorable. The proof that the number of edges is less than 1 2 (k + 5)n goes as follows. We first obtain a series of linear inequalities relating the different types of intersection points, then we relax all parameters (to be real numbers instead of integers) and observe that in order to maximize the number of edges in this linear relaxation, the intersection points have to be very specific (and in this case bounding the maximum number of edges is an easy task). I will only add that in order to prove fairly tight linear inequalities we need to make some local modifications in our k-touching family of segments. It is not easy to see that these modifications preserve the property that the objects we consider are segments. To prove it, we use a nice result of de Fraysseix and Ossona de Mendez [START_REF] De Fraysseix | Barycentric systems and stretchability[END_REF] telling when a touching family of strings can be stretched, i.e. continuously modified into a touching family of segments.

We also constructed a k-touching family of strings requiring at least 9 2 (k -1) colors, for any odd k. The construction is as follows. For some odd integer k = 2 + 1, consider n touching strings s 1 , . . . , s n that all intersect n points c 1 , . . . , c n in the same order (see the set of bold strings in Figure 2.5 (left), for an example when n = 4), and call this set of strings an n-braid. For some > 0, take three 2 -braids S 1 , S 2 , S 3 , and for i = 1, 2, 3, connect each of the strings of S i to a different intersection point of S i+1 (with indices taken modulo 3), while keeping the set of strings touching (see Figure 2.5, left). We call this set of touching strings a 2 -sun. Observe that a 2 -sun contains 6 strings that pairwise intersect, and that each intersection point contains at most 2 + 1 strings. Moreover, each of the 6 strings has an end that is incident to the infinite face.

We now consider three 2 -suns R 1 , R 2 , R 3 . Each of them has 6 strings with an end incident to the outerface. For each i = 1, 2, 3, we arbitrarily divide the strings leaving R i into two sets of 3 consecutive strings, say R i,i+1 and R i,i-1 . For each i = 1, 2, 3, we now take the strings of R i,i+1 and R i+1,i by pairs (one string in R i,i+1 , one string in R i+1,i ), and identify these two strings into a single string. This can be made in such a way that the resulting set of (6 × 3 )/2 = 9 strings is still (2 + 1)-touching (see Figure 2.5 (right), where the three 2 -suns are represented by dashed circles, and only the portion of the strings leaving the suns is displayed for the sake of clarity). Hence we obtain a k-touching set of 9 2 (k -1) strings that pairwise intersect, and therefore require at least 9 2 (k -1) distinct colors. Theorem 2.3.9 ( [START_REF] Fox | Touching strings[END_REF]). Any k-touching family of strings is (6ek + 1)-colorable.

Here, e ≈ 2.72 denotes the base of the natural logarithm. This theorem directly implies that each k-touching family of Jordan curves is (6ek + 1)-colorable (note that 6e ≈ 16.31). We obtained the following very mild improvement with Cames van Batenburg and Müller [START_REF] Cames Van Batenburg | Coloring Jordan regions and curves[END_REF].

Theorem 2. 3.10 ([23]). Any k-touching family of Jordan curves is 15.95k-colorable.

An interesting connection between the chromatic number of k-touching families of Jordan curves and the packing of directed cycles in directed planar graphs was observed by Reed and Shepherd in [START_REF] Reed | The Gallai-Younger conjecture for planar graphs[END_REF]. In a planar digraph G, let ν(G) be the maximum number of vertex-disjoint directed cycles. This quantity has a natural linear relaxation, where we seek the maximum ν * (G) for which there are weights in [0, 1] on each directed cycle of G, summing up to ν * (G), such that for each vertex v of G, the sum of the weights of the directed cycles containing v is at most 1. It was observed by Reed and Shepherd [START_REF] Reed | The Gallai-Younger conjecture for planar graphs[END_REF] that for any G there are integers n and k such that ν * (G) = n k and G contains a collection of n pairwise non-crossing directed cycles (counted with multiplicities) such that each vertex is in at most k of the directed cycles. If we replace each directed cycle of the collection by its image in the plane, we obtain a k-touching family of Jordan curves. Assume that this family is β k-colorable, for some constant β. Then the family contains an independent set (a set of pairwise non-intersecting Jordan curves) of size at least n/(β k). This independent set corresponds to a packing of directed cycles in G. As a consequence, ν(G) n/(β k) = ν * (G)/β, and then ν * (G) β ν(G). The following is therefore a direct consequence of Theorem 2.3.10. This improves a result of Reed and Shepherd [START_REF] Reed | The Gallai-Younger conjecture for planar graphs[END_REF], who proved that for any planar directed graph G, ν * (G) 28 • ν(G). Using classical results of Goemans and Williamson [START_REF] Goemans | Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs[END_REF], Theorem 2.3.11 also gives improved bounds on the ratio between the maximum packing of directed cycles in planar digraphs and the dual version of the problem, namely the minimum number of vertices that needs to be removed from a planar digraph G in order to obtain an acyclic digraph. Let us denote this parameter by τ (G), and note that the problem of finding τ (G) is also known as the Feedback Vertex Set Problem. Before we return to geometric intersection graphs, let me just mention one related result.

For a digraph G, let τ * (G) denote the the infimum real number x for which there are weights in [0, 1] on each vertex of G, summing up to x, such that for each directed cycle C, the sum of the weights of the vertices lying on C is at least 1. It follows from the linear programming duality that for any digraph G, τ * (G) = ν * (G). Goemans and Williamson [START_REF] Goemans | Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs[END_REF] conjectured that for any planar digraph G, τ (G)

3 2 τ * (G).
If a planar digraph G has n vertices and digirth at least g (i.e. if all the directed cycles of G have length at least g), then clearly τ * (G) n g (this can be seen by assigning weight 1 g to each vertex). Therefore, a direct consequence of the conjecture of Goemans and Williamson would be that if G is a planar digraph on n vertices with digirth at least g, then τ (G) 3n 2g . With Lemoine and Maffray [START_REF] Esperet | Small feedback vertex sets in planar digraphs[END_REF], we proved the following, improving results of Golowich and Rolnick [START_REF] Golowich | Acyclic Subgraphs of Planar Digraphs[END_REF].

Theorem 2.3.12 ( [START_REF] Esperet | Small feedback vertex sets in planar digraphs[END_REF]). For any n 3 and g 6, any planar digraph G with n vertices and digirth at least g satisfies τ (G) 2n-6 g . To prove Theorem 2.3.12, we first showed that a maximum packing of arc-disjoint directed cycles in an n-vertex planar digraph contains at most 2n-6 g arcs, and then used a theorem of Lucchesi and Younger [START_REF] Lucchesi | A minimax theorem for directed graphs[END_REF], which implies that for planar digraphs, the size of a minimum feedback arc-set is equal to the maximum number of pairwise arc-disjoint directed cycles.

A construction of Knauer, Valicov and Wenger [START_REF] Knauer | Planar digraphs without large acyclic sets[END_REF] shows a lower bound of n-1 g-1

(for all g 3 and infinitely many values of n) for the bound of Theorem 2.3.12.

We now return to our original problem of coloring strings. In the remainder, the strings we consider are not necessarily touching. Since it is possible to construct sets of pairwise intersecting (straight-line) segments of any size, the chromatic number of sets of segments in the plane is unbounded in general. However, Erdős conjectured that triangle-free intersection graphs of segments in the plane have bounded chromatic number (see [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]). This was recently disproved [START_REF] Pawlik | Triangle-free intersection graphs of line segments with large chromatic number[END_REF] (see [START_REF] Pawlik | Triangle-free geometric intersection graphs with large chromatic number[END_REF] for a follow-up). This construction has important consequences, which we explain below.

A class of graph is χ-bounded if there is a function f such that every graph G in the class satisfies χ(G) f (ω(G)). It is well known that the class of all graphs is not χ-bounded [START_REF] Mycielski | Sur le coloriage des graphes[END_REF]. Recall that for a given graph H, we say that a graph G is H-free if it does not contain H as an induced subgraph. Gyárfás [START_REF] Gyárfás | On Ramsey covering numbers, Infinite and Finite Sets[END_REF] (see also [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]) conjectured the following: Conjecture 2.3.13 ([88]). For any tree T , the class of T -free graphs is χ-bounded.

This conjecture is still open, but Scott [START_REF] Scott | Induced trees in graphs of large chromatic number[END_REF] proved the following topological variant in 1997: for any tree T , the class of graphs that do not contain any subdivision of T as an induced subgraph is χ-bounded. Scott conjectured that the same property should hold whether T is a tree or not. Conjecture 2.3.14 ([172]). For any H, the class of graphs excluding all subdivisions of H as an induced subgraph is χ-bounded.

On the other hand, it is easy to see that the statement of Gyárfás's conjecture is false if T contains a cycle, as there are graphs of arbitrarily high girth (ensuring no copy of T appears) and high chromatic number [START_REF] Erdős | Graph theory and probability[END_REF]. An interesting special case of Conjecture 2.3.14 is when H is a cycle. Then the conjecture implies that for any k, the class of graphs with no induced cycle of length at least k is χ-bounded. This was originally conjectured by Gyárfás in [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF], and recently proved by Chudnovsky, Scott and Seymour [START_REF] Chudnovsky | Induced subgraphs of graphs with large chromatic number[END_REF].

A k-subdivision of a (multi)graph G is a graph obtained from G by subdividing each edge at least k times, i.e. replacing every edge of G by a path on at least k + 1 edges. Since no 1-subdivision of a non-planar graph can be represented as the intersection of arcwise connected sets in the plane (in particular, such subdivisions cannot be represented as an intersection graph of line segments) no such graph appears as an induced subgraph in the construction of [START_REF] Pawlik | Triangle-free geometric intersection graphs with large chromatic number[END_REF][START_REF] Pawlik | Triangle-free intersection graphs of line segments with large chromatic number[END_REF] of triangle-free intersection graphs of segments of arbitrary chromatic number. Therefore, this construction shows that any 1-subdivision of a non-planar multigraph is a counterexample to Conjecture 2.3.14.

With Chalopin, Li and Ossona de Mendez [START_REF] Chalopin | Restricted frame graphs and a conjecture of Scott[END_REF], we studied the construction of [START_REF] Pawlik | Triangle-free geometric intersection graphs with large chromatic number[END_REF][START_REF] Pawlik | Triangle-free intersection graphs of line segments with large chromatic number[END_REF] in more details to extract more counterexamples to Conjecture 2.3.14.

A graph obtained from a tree T by adding a vertex v adjacent to every leaf of T is called a chandelier. The vertex v is called the pivot of the chandelier. If the tree T has the property that the neighbor of each leaf has degree two, then the chandelier is a luxury chandelier. Note that any subdivision of a (luxury) chandelier is a (luxury) chandelier.

A full star-cutset in a connected graph G is a set of vertices {u} ∪ N (u) whose removal disconnects G. The vertex u is called the center of the full star-cutset and the set {u} ∪ N (u), denoted by N [u], is called the closed neighborhood of u.

Using the fact that the construction of [START_REF] Pawlik | Triangle-free geometric intersection graphs with large chromatic number[END_REF][START_REF] Pawlik | Triangle-free intersection graphs of line segments with large chromatic number[END_REF] can be obtained not only as intersection of segments, but also as very specific objects, with specific patterns of intersection, we proved the following: Theorem 2.3.15 ([24]). Every connected triangle-free graph H with no full starcutset which is neither a path on at most 4 vertices, nor a luxury chandelier is a counterexample to Scott's conjecture. While the conditions in Theorem 2.3.15 may seem technical, they still apply to a wide range of graphs, including small ones. For example, all the graphs of Figure 2.6 (as well as their subdivisions) are counterexamples to Scott's conjecture.

A tree of chandeliers is either a chandelier, or obtained from a tree of chandeliers T and a chandelier C by identifying any vertex of T with the pivot of C. A forest of chandeliers is a graphs whose connected components are tree of chandeliers. For 2-subdivisions, Theorem 2.3.15 implies the following simpler characterisation.

Theorem 2.3.16 ([24]). Assume that H is an 2-subdivision of some multigraph, and is such that the class of graphs with no induced subdivisions of H is χ-bounded.

Then H is a forest of chandeliers.

A partial converse of Theorem 2.3.16 was recently proved by Chudnovsky, Scott and Seymour [START_REF] Chudnovsky | Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings[END_REF]. It remains a tantalising open problem to prove that if H is a forest of chandeliers, then the class of graphs with no induced subdivisions of H is χ-bounded. Partial results on this problem were also (more) recently obtained by Scott and Seymour [START_REF] Scott | Induced subgraphs of graphs with large chromatic number. VI. Banana trees[END_REF].

As a partial result towards Conjecture 2.3.13, Gyárfás [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF] proved the conjecture when T is a path. Gravier, Hoàng and Maffray [START_REF] Gravier | Coloring the hypergraph of maximal cliques of a graph with no long path[END_REF] improved Gyárfás's bound slightly by proving that every graph G with no induced P k (path on k vertices) satisfies χ(G) (k -2) ω(G)-1 . One may wonder whether this exponential bound can be improved. In particular, is there a polynomial function f k such that every P k -free graph G satisfies χ(G) f k (ω(G))? A positive answer to this question would also imply that a famous conjecture due to Erdős and Hajnal [START_REF] Erdős | Ramsey-type theorems[END_REF] holds true for P k -free graphs. This conjecture states that for any graph H, there is a constant δ > 0 such that any n-vertex H-free graph contains a clique or an independent set of order at least n δ (when every H-free graph G has chromatic number at most ω(G) c , for some constant c depending only of H, this is a simple consequence of the fact that the chromatic number of a graph G on n vertices is at least n/α(G)). This conjecture is widely open (even when H is a 5-cycle or a P 5 ).

When k = 5 and ω(G) = 3, the above results imply that χ(G) 9. With Lemoine, Maffray and Morel [START_REF] Esperet | The chromatic number of {P 5 , K 4 }-free graphs[END_REF], we proved the following.

Theorem 2.3.17 ([62]). Let G be a graph with no K 4 and no induced P 5 . Then χ(G) 5. This is best possible, as shown by the graph G depicted in Figure 2.7. It is easy to check that G is K 4 -free and does not contain any induced P 5 , and that χ(G) = 5. It is not difficult to derive from Theorem 2.3.17 the following slight improvement over the bound of [START_REF] Gravier | Coloring the hypergraph of maximal cliques of a graph with no long path[END_REF] for k = 5: for any P 5 -free graph G, χ(G) 5 • 3 ω(G)-3 . A claw is the graph obtained from 3 isolated vertices by adding a fourth vertex adjacent to these 3 vertices. It is not difficult to check that every line-graph is claw-free (i.e., does not contain a claw as an induced subgraph), and therefore an important line of research has consisted in extending results on line-graphs to the class of claw-free graphs. For instance, it was conjectured by Gravier and Maffray [START_REF] Gravier | On the choice number of claw-free perfect graphs[END_REF] that every claw-free graph G satisfies ch(G) = χ(G). This conjecture generalizes the famous list coloring conjecture, stating that χ and ch coincide for line-graphs of multigraphs.

Note that a claw is a tree, and it is therefore interesting to check whether it satisfies Conjecture 2.3.13. As observed by Gyárfás, it follows from a simple Ramsey theoretic argument that claw-free graphs with bounded clique number have bounded maximum degree (and therefore bounded chromatic number). Using a deep decomposition theorem, Chudnovsky and Seymour [START_REF] Chudnovsky | Claw-free graphs VI. Coloring claw-free graphs[END_REF] proved that every connected claw-free graph G that has a stable set of size 3 satisfies χ(G) 2ω(G). They also proved that their bound is best possible when ω(G) 5. With Gyárfás and Maffray [START_REF] Esperet | List-coloring claw-free graphs with small clique number[END_REF], we improved their result when the clique number is 3 or 4 (however, our result holds for all claw-free graphs and for list-coloring instead of coloring).

Theorem 2.3.18 ([54]). Every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable.

The bounds are tight, and the proofs are fairly simple applications of well-known results in Ramsey theory.

We conclude this section with an observation. To the best of my knowledge, there is no known hereditary χ-bounded class C of graphs for which there is no constant c, such that for any graph G ∈ C, χ(G) ω(G) c . Usually the upper bounds on the χ-bounding functions are quite bad (i.e. exponential or worse), but whenever such a bound exist, the corresponding known lower bounds are polynomial. For the sake of extending our knowledge on upper bounds, I conjectured the following during a workshop on χ-bounded classes organised in Lyon, France, in March 2012. It was noted by Trotignon (personal communication) that the class of graphs with no stable sets of size k shows that the constant c in Conjecture 2.3.19 can be arbitrarily large (i.e. it cannot be replaced by an absolute constant, independent of C).

Exact distance coloring of graphs

In Section 2.2, we investigated the chromatic number of squares of graphs, i.e. graph colorings such that vertices at distance at most two receive distinct colors. In this section, we consider colorings of graphs such that vertices at distance exactly d, for some fixed integer d, have distinct colors. The problem we consider here comes from a slightly more general problem which can be raised in any metric space.

Given a metric space X and some real d > 0, let χ(X, d) be the minimum number of colors in a coloring of the elements of X such that any two elements at distance exactly d in X are assigned distinct colors. The classical Hadwiger-Nelson problem asks for the value of χ(R 2 , 1), where R 2 is the Euclidean plane. It is known that 4 χ(R 2 , 1) 7 and since the Euclidean plane R 2 is invariant under homothety, χ(R 2 , 1) = χ(R 2 , d) for any real d > 0. Let H 2 denote the hyperbolic plane. Kloeckner [START_REF] Kloeckner | Coloring distance graphs: a few answers and many questions[END_REF] proved that χ(H 2 , d) is at most linear in d (the multiplicative constant was recently improved by Parlier and Petit [START_REF] Parlier | Chromatic numbers for the hyperbolic plane and discrete analogs[END_REF]), and observed that χ(H 2 , d) 4 for any d > 0. He raised the question of determining whether χ(H 2 , d) grows with d or can be bounded independently of d. As noticed by Kahle (see [START_REF] Kloeckner | Coloring distance graphs: a few answers and many questions[END_REF]), it is not known whether χ(H 2 , d) 5 for some real d > 0. Parlier and Petit [START_REF] Parlier | Chromatic numbers for the hyperbolic plane and discrete analogs[END_REF] recently suggested to study infinite regular trees as a discrete analog of the hyperbolic plane. Note that any graph G can be considered as a metric space (whose elements are the vertices of G and whose metric is the graph distance in G), and in this context χ(G, d) is precisely the minimum number of colors in a vertex coloring of G such that vertices at distance d apart are assigned different colors. Note that χ(G, d) can be equivalently defined as the chromatic number of the exact d-th power of G, that is, the graph with the same vertex-set as G in which two vertices are adjacent if and only if they are at distance exactly d in G.

Let T q denote the infinite q-regular tree. Parlier and Petit [START_REF] Parlier | Chromatic numbers for the hyperbolic plane and discrete analogs[END_REF] observed that when d is odd, χ(T q , d) = 2 and proved that when d is even, q χ(T q , d) (d + 1)(q -1). A similar upper bound can also be deduced from the results of van den Heuvel, Kierstead and Quiroz [START_REF] Van Den Heuvel | Chromatic Numbers of Exact Distance Graphs[END_REF], while the lower bound is a direct consequence of the fact that when d is even, the clique number of the exact d-th power of T q is q (note that it does not depend on d). With Bousquet, Harutyunyan and de Joannis de Verclos [START_REF] Bousquet | Exact distance coloring in trees[END_REF], we proved the following.

Theorem 2.4.1 ([22]). For fixed q 3, and any even integer d,

d log(q-1) 4 log(d/2)+4 log(q-1) χ(T q , d) (2 + o(1)) d log(q-1) log d ,
where the asymptotic o( 1) is in terms of d.

A byproduct of the proof of our result is that for any even integer d, the exact d-th power of a complete binary tree of depth d is of order Θ(d/ log d) (while its clique number is equal to 3).

The following problem (attributed to van den Heuvel and Naserasr) was raised in [START_REF] Nešetřil | Sparsity -Graphs, Structures, and Algorithms[END_REF] (see also [START_REF] Van Den Heuvel | Chromatic Numbers of Exact Distance Graphs[END_REF] and [START_REF] Nešetřil | On low tree-depth decompositions[END_REF]).

Problem 2.4.2 (Problem 11.1 in [START_REF] Nešetřil | Sparsity -Graphs, Structures, and Algorithms[END_REF]). Is there a constant C such that for every odd integer d and every planar graph G we have χ(G, d) C? Our result on large complete binary trees easily implies a negative answer to Problem 2.4.2. More precisely, we proved that the graph U d obtained from a complete binary tree of depth d by adding an edge between any two vertices with the same parent gives a negative answer to Problem 2.4.2 (in particular, for odd d, the chromatic number of the exact d-th power of U d grows as Θ(d/ log d)). We also proved that the exact d-th power of a specific subgraph Q d of U d grows as Ω(log d). Note that U d and Q d are outerplanar (and thus, planar) and chordal (see Figure 2.8).

Improper coloring of graphs on surfaces 2.5.1 Components of bounded size

Recall that in a proper coloring of a graph G, each color class is an independent set. In other words, in each color class, connected components consist of singletons. In this section we investigate a relaxed version of this classical version of graph coloring, where connected components in each color class, called monochromatic components, have bounded size.

The famous HEX Lemma implies that in every 2-coloring of the triangular k × kgrid, there is a monochromatic path on k vertices. This shows that planar graphs with maximum degree 6 cannot be 2-colored in such a way that all monochromatic components have bounded size. On the other hand, Haxell, Szabó and Tardos [START_REF] Haxell | Bounded size components-partitions and transversals[END_REF] proved that every (not necessarily planar) graph with maximum degree at most 5 can be 2-colored in such a way that all monochromatic components have size at most 20000.

As for three colors, Kleinberg, Motwani, Raghavan, and Venkatasubramanian [119, Theorem 4.2] constructed planar graphs that cannot be 3-colored in such a way that each monochromatic component has bounded size. However, their examples have large maximum degree, which prompted them to ask the following question. Question 2.5.1 ([119]). Is there a function f : N → N such that every planar graph with maximum degree at most ∆ has a 3-coloring in which each monochromatic component has size at most f (∆)?

A similar construction was given by Alon, Ding, Oporowski and Vertigan [3, Theorem 6.6], who also pointed that they do not know whether examples with bounded maximum degree can be constructed. Question 2.5.1 was also raised more recently by Linial, Matoušek, Sheffet and Tardos [START_REF] Linial | Graph coloring with no large monochromatic components[END_REF].

With Joret [START_REF] Esperet | Coloring planar graphs with three colors and no large monochromatic components[END_REF], we gave a positive answer to Question 2.5.1.

Theorem 2.5.2 ([56]

). There exists a function f : N → N such that every planar graph with maximum degree ∆ has a 3-coloring in which each monochromatic component has size at most f (∆). Theorem 2.5.3 is proved by induction on the number of vertices of G. We first prove that we can assume that G is a near-triangulation (i.e. all faces except possibly the outerface are triangular). Then there are two cases: If the outerface O(G) induces a cycle, we delete all the vertices of O(G) and apply induction (this is the most technical part), and obtain bounds that are significantly better than the final bounds we want to prove for the general case. If the outerface O(G) does not induce a cycle, there must be a chord or a cut-vertex. By choosing such a chord or cut-vertex in a careful way, we can divide G into two parts G 1 and G 2 (whose intersection is a clique-cutset C of order 1 or 2) such that one of the two parts, say G 2 is such that O(G 2 ) induces a cycle. We now apply the induction to G 1 and G 2 . Since O(G 2 ) induces a cycle, the bounds we obtain from the induction are better than what we need at the end, and in particular we can recolor C and the neighbors of C in G 2 such that the colorings of G 1 and G 2 coincide on C and when we glue G 1 and G 2 on C, the order of monochromatic components does not increase.

It is not difficult to extend Theorem 2.5.2 to graphs embeddable on a fixed surface (by repeatedly cutting the graph along a shortest non-contractible cycle). For graphs embedded on a surface of Euler genus g, we obtain a bound of (5∆) 2 g -1 f (∆) 2 g on the order of monochromatic components, where f (∆) = (15∆) 32∆+8 is the function of Theorem 2.5.2. Using a more involved cutting technique of Kawarabayashi and Thomassen [START_REF] Kawarabayashi | From the plane to higher surfaces[END_REF] (which we will see again in the next section) together with the stronger property from Theorem 2.5.3 that one color can be omitted on the outerface, it is possible to obtain a bound that is linear in the genus. Theorem 2.5.4 ( [START_REF] Esperet | Coloring planar graphs with three colors and no large monochromatic components[END_REF]). Every graph G with maximum degree ∆ 1 embedded in a surface of Euler genus g can be 3-colored in such a way that each monochromatic component has size at most f (∆) + 20∆(f (∆) + 2)(∆f (∆) + 1) g, where f (∆) = (15∆) 32∆+8 . Theorem 2.5.4 was recently extended to all proper minor-closed classes by Liu and Oum [START_REF] Liu | Partitioning H-minor free graphs into three subgraphs with no large components[END_REF]. Their proof is based on the structure theorem of Robertson and Seymour (or rather, the large tree-width version of the theorem), and uses Theorem 2.5.4.

Theorem 2.5.5 ([133]). For every proper minor-closed class of graphs G, there is a function f G : N → N such that every graph in G with maximum degree ∆ can be 4-colored in such way that each monochromatic component has size at most f G (∆) This improves a result of Alon, Ding, Oporowski and Vertigan [START_REF] Alon | Partitioning into graphs with only small components[END_REF], who proved that for every proper minor-closed class of graphs G, there is a function f G : N → N such that every graph in G with maximum degree ∆ can be 4-colored in such way that each monochromatic component has size at most f G (∆).

Recall that Kleinberg, Motwani, Raghavan, and Venkatasubramanian [START_REF] Kleinberg | Storage management for evolving databases[END_REF] and Alon, Ding, Oporowski, and Vertigan [START_REF] Alon | Partitioning into graphs with only small components[END_REF], constructed families of planar graphs that cannot be colored with 3 colors in such a way that all monochromatic components have bounded size. These examples can easily be generalised to families of graphs with no K t -minors that cannot be colored with t -2 colors in such a way that all monochromatic components have bounded size. This shows that the famous Hadwiger conjecture, stating that graphs with no K t -minor have a proper coloring with t -1 colors, is best possible even if we only ask the sizes of monochromatic components to be bounded by a function of t (instead of being of size 1). The best known bound (on the number of colors) for the Hadwiger conjecture is O(t √ log t) (see [START_REF] Kostochka | Lower bound of the Hadwiger number of graphs by their average degree[END_REF][START_REF] Thomason | An extremal function for contractions of graphs[END_REF]). On the other hand, Kawarabayashi and Mohar [START_REF] Kawarabayashi | A relaxed Hadwiger's conjecture for list colorings[END_REF] proved the existence of a function f such that every K t -minor-free graph has a coloring with 31 2 t colors in which each monochromatic component has size at most f (t). This bound was reduced to 7 2 t -3 2 colors by Wood [START_REF] Wood | Contractibility and the Hadwiger Conjecture[END_REF]. Liu and Oum [START_REF] Liu | Partitioning H-minor free graphs into three subgraphs with no large components[END_REF] observed that by combining Theorem 2.5.5 with a result of [START_REF] Edwards | A relative of Hadwiger's conjecture[END_REF] (stating that K t -minor free graphs have a (t -1)-coloring in which each monochromatic component has bounded degree, see Section 2.5.2), we easily deduce that every K t -minor-free graph has a coloring with 3t -3 colors in which each monochromatic component has bounded size. Norin [START_REF] Norin | Conquering graphs of bounded treewidth[END_REF] later improved the bound to 2t -2. More recently, van den Heuvel and Wood [START_REF] Van Den Heuvel | Improper Colourings inspired by Hadwiger's Conjecture[END_REF] obtained the same bound with a very simple argument, that does not involve any result from the Graph Minors series of Robertson and Seymour (in particular, their bound on the maximum size of the monochromatic components is very reasonable, unlike in all the other results mentioned in this paragraph). Finally, Dvořák and Norin recently announced a proof that every K t -minor-free graph has a coloring with t -1 colors in which each monochromatic component has bounded size (i.e. they claim that they proved the bounded-size component version of the Hadwiger conjecture, and as explained above, their result would be best possible).

With Ochem [START_REF] Esperet | Islands in graphs on surfaces[END_REF], we proved that this bound of t -1 colors can be significantly improved in the case of graphs embeddable on a fixed surface. It was proved by Thomassen [START_REF] Thomassen | Every planar graph is 5-choosable[END_REF] that every planar graph G is 5-choosable (i.e. for every 5-list assignment L, the graph G has a proper L-coloring). We proved that the same holds for any graph embeddable on a surface of genus g, provided that monochromatic components are only required to have size bounded by O(g). The fact that cliques of order Ω( √ g) can be embedded on such surfaces shows that the size of monochromatic components has to depend on g.

Theorem 2.5.6 ( [START_REF] Esperet | Islands in graphs on surfaces[END_REF]). For any integer g, for any graph G that can be embedded on a surface of Euler genus g, and any 5-list assignment L, G has an L-coloring in which every monochromatic component has size at most max (3, 72g -144). Moreover, all vertices except at most max(0, 72g -144) of them lie in monochromatic components of size at most 3.

In [START_REF] Chappell | On Subgraphs Without Large Components[END_REF], Chappell and Gimbel conjectured that for any fixed surface Σ there is a constant k such that every graph embeddable on Σ can be 5-colored without monochromatic components of size more than k. Note that Theorem 2.5.6 proves their conjecture in a strong sense.

Cushing and Kierstead [START_REF] Cushing | Planar graphs are 1-relaxed, 4-choosable[END_REF] proved that for every planar graph G and every 4-list assignment L to the vertices of G, there is an L-coloring of G in which each monochromatic component has size at most 2. Hence, Theorem 2.5.6 restricted to planar graphs is significantly weaker than their result. We conjectured the following:

Conjecture 2.

([68]

). There is a function f such that for any integer g, for any graph G that can be embedded on a surface of Euler genus g, and any 4-list assignment L, G has an L-coloring in which every monochromatic component has size at most f (g).

Kawarabayashi and Thomassen [START_REF] Kawarabayashi | From the plane to higher surfaces[END_REF] proved that every graph that has an embedding on a surface of Euler genus g can be colored with colors 1, 2, 3, 4, 5, in such a way that each color i 4 is an independent set, while color 5 induces a graph in which each connected component contains O(g 2 ) vertices. A small variation in the proof of Theorem 2.5.6 shows the following corollary.

Corollary 2.5.8 ( [START_REF] Esperet | Islands in graphs on surfaces[END_REF]). Every graph that has an embedding on a surface of Euler genus g can be colored with colors 1, 2, 3, 4, 5, in such a way that each color i 4 induces a graph in which each connected component has size at most 3, while color 5 induces a graph in which each connected component contains O(g) vertices.

A theorem of Grötzsch [START_REF] Grötzsch | Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF] asserts that every triangle-free planar graph has a proper 3-coloring. On the other hand, Škrekovski [START_REF] Škrekovski | List improper colourings of planar graphs[END_REF] proved that there is no constant c for which every triangle-free planar graph can be 2-colored such that every monochromatic component has degree at most c. In particular , the same holds with degree replaced by size. Hence, it follows again that Grötzsch's theorem cannot be improved even in our relaxed setting. We proved however that every triangle-free graph embeddable on a surface of genus g can be colored from any 3-list assignment, in such a way that all monochromatic components have size O(g). Theorem 2.5.9 ( [START_REF] Esperet | Islands in graphs on surfaces[END_REF]). For any integer g, for any triangle-free graph G that can be embedded on a surface of Euler genus g, and any 3-list assignment L, G has an Lcoloring in which every monochromatic component has size at most max (10, 72g-144). Moreover, all vertices except at most max(0, 72g -144) of them lie in monochromatic components of size at most 10.

The case of triangle-free graphs is particularly interesting because Voigt [START_REF] Voigt | A not 3-choosable planar graph without 3-cycles[END_REF] proved that there exists a triangle-free planar graph G and a 3-list assignment L such that G is not L-colorable. So our result is non-trivial (and previously unknown, as far as we are aware of) even in the case of planar graphs.

We conjectured the following: Conjecture 2.5.10 ( [START_REF] Esperet | Islands in graphs on surfaces[END_REF]). There is a function f such that for any integer g, for any graph G of girth at least 5 that can be embedded on a surface of Euler genus g, and any 2-list assignment L, G has an L-coloring in which every monochromatic component has size at most f (g).

We proved this conjecture for graphs of girth at least 6 (instead of 5).

Theorem 2.5.11 ([68]). For any integer g, for any graph G of girth at least 6 that can be embedded on a surface of Euler genus g, and any 2-list assignment L, G has an L-coloring in which every monochromatic component has size at most max (16, 357g -714). Moreover, all vertices except at most max(0, 357g -714) of them lie in monochromatic components of size at most 16.

For planar graphs, the bound on the size of monochromatic components can be slightly improved.

Theorem 2.5.12 ( [START_REF] Esperet | Islands in graphs on surfaces[END_REF]). For any planar graph G of girth at least 6 and any 2-list assignment L, G has an L-coloring in which every monochromatic component has size at most 12.

Note that it was proved by Borodin, Kostochka and Yancey [START_REF] Borodin | On 1-improper 2-coloring of sparse graphs[END_REF] that every planar graph of girth at least 7 has a 2-coloring in which every monochromatic component has size at most 2.

After our paper was submitted, interesting results in connection with Conjecture 2.5.10 were proved. In [START_REF] Axenovich | Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths[END_REF], Axenovich, Ueckerdt, and Weiner proved the following strong variant of Theorem 2.5.12: any planar graph of girth at least 6 has a 2-coloring such that each monochromatic component is a path on at most 14 vertices. More recently, Dvořák and Norin observed that Conjecture 2.5.10 follows as a byproduct of their (announced) proof that every K t -minor-free graph has a coloring with t -1 colors in which each monochromatic component has bounded size. Theorems 2.5.6, 2.5.9, 2.5.11, 2.5.12 as well as the recently announced proof of Conjecture 2.5.10 by Dvořák and Norin, are simple consequences of purely structural results on (large) graphs embeddable on surfaces of bounded genus. Given a graph G, a k-island of G is a non-empty set X of vertices of G such that each vertex of X has at most k neighbors outside X in G. The size of a k-island is the number of vertices it contains. A simple proof by induction shows that if each subgraph of a given graph G contains a k-island of size at most , then G has a coloring with k + 1 colors such that each monochromatic component has size at most . This can be seen as an extension of the notion of degeneracy to the problem of coloring with monochromatic components of bounded size.

With Ochem [START_REF] Esperet | Islands in graphs on surfaces[END_REF], we proved that: (1) large graphs of bounded genus have a 4-island of size at most 3;

(2) large triangle-free graphs of bounded genus have a 2-island of size at most 10;

(3) large graphs of girth at least 6 and bounded genus have a 1-island of size at most 16; and (4) large planar graphs of girth at least have a 1-island of size at most 12.

The proofs of these four results use the discharging method in a fairly standard way.

Recall that it was proved by Grötzsch [START_REF] Grötzsch | Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF] that triangle-free planar graphs are 3colorable, while it was proved by Škrekovski [START_REF] Škrekovski | List improper colourings of planar graphs[END_REF] that there is no constant c for which every triangle-free planar graph can be 2-colored such that every monochromatic component has size at most c. All known constructions (see also [START_REF] Esperet | Coloring planar graphs with three colors and no large monochromatic components[END_REF]) have unbounded maximum degree. Hence, the following natural question remains open. Question 2.5.13 ([56]). Is there a function f : N → N such that every triangle-free planar graph with maximum degree ∆ can be 2-colored in such a way that each monochromatic component has size at most f (∆)?

We conclude this section with two results regarding the complexity of the problem of bounding the size of monochromatic components in a 2-coloring of a graph. Let us define an M C(k)-coloring as a 2-coloring such that every monochromatic component has size at most k. Let MC(k) be the class of graphs having an M C(k)-coloring.

With Ochem [START_REF] Esperet | Islands in graphs on surfaces[END_REF], we proved that approximating the minimum k such that a graph G has an M C(k)-coloring is a hard problem. Theorem 2.5.14 ([68]). Let k 2 be a fixed integer. The following problems are NP-complete.

1. Given a 2-degenerate graph with girth at least 8 that either is in MC(2) or is not in MC(k), determine whether it is in MC(2).

2. Given a 2-degenerate triangle-free planar graph that either is in MC(k) or is not in MC(k(k -1)), determine whether it is in MC(k).

Components of bounded degree

For a sequence (d [START_REF] Edwards | A relative of Hadwiger's conjecture[END_REF], mentioned in the previous section, and stating that for any t, there is a d such that every K t -minor free graph has a d-defective (t -1)-coloring (this can be seen as a defective version of the Hadwiger conjecture). This result has a 2-page proof using a fairly simple density argument, while the analogous result in the bounded size component case (whose proof was recently announced by Dvořák and Norin) requires much deeper tools.

The Four Color Theorem is equivalent to the statement that every planar graph is (0, 0, 0, 0)-colorable, and it was proved by Cowen, Cowen and Woodall [START_REF] Cowen | Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency[END_REF] that every planar graph is also (2, 2, 2)-colorable. For any integer k, it is not difficult to construct a planar graph that is not (k, k)-colorable; one can even find such planar graphs that are triangle-free (see [START_REF] Škrekovski | List improper colourings of planar graphs[END_REF]).

A natural question to ask is how these results can be extended to graphs embeddable on surfaces with higher genus. Cowen, Cowen and Woodall [START_REF] Cowen | Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency[END_REF] proved that every graph of Euler genus g is (c 4 , c 4 , c 4 , c 4 )-colorable with c 4 = max{14, 1 3 (4g -11)}, and conjectured that the same should hold with three colors instead of four. This was proved by Archdeacon [START_REF] Archdeacon | A note on defective colorings of graphs in surfaces[END_REF], who showed that every graph of Euler genus g is (c 3 , c 3 , c 3 )-colorable with c 3 = max{15, 1 2 (3g -8)}. The value c 3 was subsequently improved to max{12, 6 + √ 6g} by Cowen, Goddard and Jesurum [START_REF] Cowen | Defective coloring revisited[END_REF], and eventually to max{9, 2 + √ 4g + 6} by Woodall [START_REF] Woodall | Defective choosability of graphs in surfaces[END_REF]. With Choi [START_REF] Choi | Improper coloring of graphs on surfaces[END_REF], we proved that in the original result of Cowen, Cowen, and Woodall [START_REF] Cowen | Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency[END_REF], it suffices that only one of the four color classes is not a stable set.

Theorem 2.5.15 ([27]). For each g > 0, every graph of Euler genus g has a (0, 0, 0, 9g -4)-coloring.

Theorem 2.5.16 ([27]). For each g > 0, every graph of Euler genus g has a (2, 2, 9g -4)-coloring. These two theorems are fairly simple consequences of the following result (combined with the Four color theorem and the fact that planar graphs are (2, 2, 2)colorable [START_REF] Cowen | Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency[END_REF]).

Theorem 2.5.17 ([27]). For every g > 0, every connected graph G of Euler genus g, and every vertex v of G, the graph G has a connected subgraph H containing v, such that G/H is planar and every vertex of G has at most 9g -4 neighbors in H.

The proof of this result uses similar ideas as the cutting technique developed by Kawarabayashi and Thomassen [START_REF] Kawarabayashi | From the plane to higher surfaces[END_REF], and mentioned in the previous section.

Interestingly, there is a constant c 1 > 0 such that the bound 9g -4 in these results cannot be replaced by c 1 • g, so there is no hope to obtain a bound of the same order as c 3 above. In other words, the growth rate of the bound 9g -4 cannot be improved to a sublinear function of g in both results.

However, when two color classes are allowed to have non-constant maximum degrees, we proved that the bound 9g -4 can be improved to a sublinear function of g in both results.

Theorem 2.5.18 ([27]). Every graph embeddable on a surface of Euler genus g is (0, 0, K 2 , K 2 )-colorable, with K 1 = K 1 (g) = 20 + √ 48g + 481.

Theorem 2.5.19 ([27]). Every graph embeddable on a surface of Euler genus g is

(2, K 1 , K 1 )-colorable where K 2 = K 2 (g) = 38 + √ 84g + 1682.
We also showed that the growth rate of K 1 (g) and K 2 (g) are tight in terms of g. Recall that Grötzsch [START_REF] Grötzsch | Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF] proved that every triangle-free planar graph is 3-colorable. We proved that this can be extended to graphs embeddable on surfaces as follows:

Theorem 2.5.20 ([27]). Every triangle-free graph embeddable on a surface of Euler genus g is (0, 0, K 3 )-colorable where

K 3 = K 3 (g) = 10g+32 3 .
We also proved that K 3 (g) cannot be replaced by a sublinear function of g, even for graphs of girth at least 6. It was proved by Škrekovski [181] that for any k, there exist triangle-free planar graphs that are not (k, k)-colorable. This shows that there does not exist any 2-color analogue of our result on triangle-free graphs on surfaces.

Choi, Choi, Jeong and Suh [START_REF] Choi | 1, k)-coloring of graphs with girth at least 5 on a surface[END_REF] proved that every graph of girth at least 5 embeddable on a surface of Euler genus g is (1, K 4 (g))-colorable where K 4 (g) = max{10, 12g+47 7 }. They also showed that the growth rate of K 4 (g) cannot be replaced by a sublinear function of g. On the other hand, for each k, Borodin, Ivanova, Montassier, Ochem and Raspaud [START_REF] Borodin | Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k[END_REF] constructed a planar graph of girth 6 that is not (0, k)-colorable.

Finally, we proved the following for graphs of girth at least 7.

Theorem 2.5.21 ([27]). Every graph of girth at least 7 embeddable on a surface of Euler genus g is (0, K 5 )-colorable where

K 5 = K 5 (g) = 5 + √ 14g + 22 .
On the other hand, we showed that there is a constant c 2 > 0 such that for infinitely many values of g, there exist graphs of girth at least 7 embeddable on a surface of Euler genus g, with no (0, c 2 √ g )-coloring.

The proofs of Theorems 2.5.19, 2.5.18, 2.5.20, and 2.5.21 all follow from fairly simple discharging arguments.

Our results, together with the aforementioned results, completely solve the following problem (up to a constant multiplicative factor for the maximum degrees d i , depending on g): given integers 7, k, and g, find the smallest k-tuple (d 1 , . . . , d k ) in lexicographic order, such that every graph of girth at least embeddable on a surface of Euler genus g is (d 1 , . . . , d k )-colorable.

A natural question is to find a version of Theorem 2.5.21 for graphs of arbitrary large girth. A slight variation of the proof of Theorem 2.5.21 easily shows that a graph of girth at least embeddable on a surface of Euler genus g is (0, O( g/ ))-colorable, where the hidden multiplicative constant is independent of g and . We conjectured the following stronger statement.

Conjecture 2.5.22 ([27]

). There is a function c = o(1) such that any graph of girth at least embeddable on a surface of Euler genus g is (0, O(g c( ) ))-colorable. It was recently observed by Dross that our original proof of Theorem 2.5.21 can be modified easily to show that any graph of girth at least embeddable on a surface of Euler genus g is (0, O(g 6/( +5) ))-colorable, which proves Conjecture 2.5.22. Note that a graph that is (0, k)-colorable has a proper coloring with k + 2 colors (since a graph with maximum degree k has a proper (k + 1)-coloring). As a consequence, the following result of Gimbel and Thomassen [START_REF] Gimbel | Coloring graphs with fixed genus and girth[END_REF] gives a lower bound of order Ω(g 1/(2 +2) ) for this problem as well.

Theorem 2.5. 23 ([80]). For any , there exist a constant c > 0 such that for arbitrarily small > 0 and sufficiently large g, there are graphs of girth at least embeddable on surfaces of Euler genus g that have no proper coloring with less than c g 1-2 +2 colors.

We conclude this section with a complexity result on (0, 1)-coloring. Let C g,d denote the class of planar graphs with girth at least g and maximum degree at most d. With Montassier, Ochem, and Pinlou [START_REF] Esperet | A complexity dichotomy for the coloring of sparse graphs[END_REF], we observed the following interesting dichotomy.

Theorem 2.5.24 ([67]). Let g 6 and d 3 be integers. Either every graph in C g,d is (0, 1)-colorable, or deciding whether a graph in

C g,d is (1, 0)-colorable is NP-complete.
This kind of complexity jump appears in different contexts. Let (k, s)-SAT denote the Boolean satisfiability problem restricted to instances with exactly k variables per clause, and at most s occurrences per variable. Tovey [START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF] proved that (3, 4)-SAT is NP-complete, while (3, 3)-SAT is trivial (every instance is satisfiable). This was generalized by Kratochvíl, Savický and Tuza [START_REF] Kratochvíl | One more occurrence of variables makes satisfiability jump from trivial to NP-complete[END_REF], who proved the existence of a function f (of exponential order) such that for any k 3, (k, f (k) + 1)-SAT is NP-complete, while (k, f (k))-SAT is trivial. The reader is referred to [START_REF] Gebauer | The Local Lemma is Tight for SAT[END_REF] for a more detailed discussion about these results, together with the precise asymptotics for the function f (which is closely related to functions appearing in the Lovász Local Lemma). The specificity of Theorem 2.5.24, compared with the example above, is that the dichotomy is 2-dimensional.

By constructing two planar graphs of specific girth and maximum degree that are not (0, 1)-colorable, we directly obtained the following two corollaries of Theorem 2.5.24.

Corollary 2.5. 25 ([67]). Deciding whether a planar graph of girth at least 7 and maximum degree at most 3 is (0, 1)-colorable is NP-complete.

Corollary 2.5.26 ([67]). Deciding whether a planar graph of girth at least 9 and maximum degree at most 4 is (0, 1)-colorable is NP-complete.

Note that Kim, Kostochka and Zhu [START_REF] Kim | Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs[END_REF] proved that every planar graph with girth at least 11 is (0, 1)-colorable. It is an open problem to determine whether all planar graphs of girth at least 10 are (0, 1)-colorable.

Two more results related to coloring problems

for graphs on surfaces 2.6.1 Odd cycles in 4-chromatic graphs

Erdős [START_REF] Erdős | Some new applications of probability methods to combinatorial analysis and graph theory[END_REF] asked whether there is a constant c such that every n-vertex 4-chromatic graph has an odd cycle of length at most c √ n. Kierstead, Szemerédi and Trotter [START_REF] Kierstead | On coloring graphs with locally small chromatic number[END_REF] proved the conjecture with c = 8, and the constant was gradually brought down to c = 2 [START_REF] Jiang | Small odd cycles in 4-chromatic graphs[END_REF][START_REF] Nilli | Short odd cycles in 4-chromatic graphs[END_REF]. A natural question, asked by Ngoc and Tuza [START_REF] Ngoc | 4-chromatic graphs with large odd girth[END_REF], is to determine the infimum of c such that every 4-chromatic graph on n vertices has an odd cycle of length at most c √ n.

A construction due to Gallai [78] shows that c > 1, and this was subsequently improved to c > √ 2 by Ngoc and Tuza [START_REF] Ngoc | 4-chromatic graphs with large odd girth[END_REF], and independently by Youngs [START_REF] Youngs | 4-chromatic projective graphs[END_REF]. The graphs they used-the so-called generalised Mycielski graphs-are a subclass of a rich family of graphs known as non-bipartite projective quadrangulations. These are graphs that embed in the projective plane so that all faces are bounded by four edges, but are not bipartite. This family of graphs plays an important role in the study of the chromatic number of graphs on surfaces: it was shown by Youngs [START_REF] Youngs | 4-chromatic projective graphs[END_REF] that all such graphs are 4-chromatic. Gimbel and Thomassen [START_REF] Gimbel | Coloring graphs with fixed genus and girth[END_REF] later proved that triangle-free projective-planar graphs are 3-colorable if and only if they do not contain a non-bipartite projective quadrangulation, and used this to show that the 3-colorability of triangle-free projective-planar graphs can be decided in polynomial time. Thomassen [START_REF] Thomassen | Quadrangulations and 4-color-critical graphs[END_REF] also used projective quadrangulations to give negative answers to two questions of Bollobás [START_REF] Bollobás | Extremal graph theory[END_REF] about 4-chromatic graphs.

Let G be a non-bipartite projective quadrangulation. A key property of such a graph is that any cycle in G is contractible on the surface if and only if it has even length. In particular, the length of a shortest odd cycle in G is precisely the edge-width of G (i.e. the length of a shortest non-contractible cycle). Since any two non-contractible closed curves on the projective plane intersect, it also follows that G does not contain two vertex-disjoint odd cycles. The interest in the study of odd cycles in 4-colorable graphs also comes from the following question of Erdős [START_REF] Erdős | Problem 2, In Theory of Graphs[END_REF]: does every 5-chromatic K 5 -free graph contain a pair of vertex-disjoint odd cycles? Erdős's question may be rephrased as follows: is every K 5 -free graph without two vertex-disjoint odd cycles 4-colorable? This was answered in the affirmative by Brown and Jung [START_REF] Brown | On odd circuits in chromatic graphs[END_REF]. The non-bipartite projective quadrangulations provide an infinite family of graphs showing that 4 cannot be replaced by 3. Note that Erdős's question was generalised by Lovász and became known as the Erdős-Lovász Tihany Conjecture. So far only a few cases of the conjecture have been proved.

With Stehlík [START_REF] Esperet | The width of quadrangulations of the projective plane[END_REF], we settled the problem of Ngoc and Tuza [START_REF] Ngoc | 4-chromatic graphs with large odd girth[END_REF] for the case of 4-chromatic graphs with no two vertex-disjoint odd cycles (and in particular, for non-bipartite projective quadrangulations).

Theorem 2.6.1 ([69]). Let G be a 4-chromatic graph on n vertices without two vertexdisjoint odd cycles. Then G contains an odd cycle of length at most 1 2 (1 + √ 8n -7).

We proved this result using a theorem of Lins [START_REF] Lins | A minimax theorem on circuits in projective graphs[END_REF] on graphs embedded in the projective plane (an equivalent form of the Okamura-Seymour theorem in Combinatorial Optimisation), and the Two Disjoint Odd Cycles Theorem of Lovász. Note that in the generalised Mycielski graphs found by Ngoc and Tuza [START_REF] Ngoc | 4-chromatic graphs with large odd girth[END_REF], and independently by Youngs [START_REF] Youngs | 4-chromatic projective graphs[END_REF] (such a graph is depicted in Figure 2.9, right), the shortest odd cycles have precisely 1 2 (1 + √ 8n -7) vertices, so Theorem 2.6.1 is sharp for infinitely many values of n. A natural question is whether generalised Mycielski graphs are the only extremal graphs for this problem.

An odd cycle transversal in a graph G is a set S of vertices such that G -S is bipartite. Since any two odd cycles intersect in a non-bipartite projective quadrangulation G, it follows that any odd cycle in G is also an odd cycle transversal of G. The following slightly more general result holds. If γ is a non-contractible closed curve whose intersection with G is a subset S ⊆ V (G) (recall that the minimum size of such a set S is called the face-width of G), then G -S is bipartite. It follows that the minimum size of an odd cycle transversal of G cannot exceed the face-width of G, and it can be proved that the two parameters are indeed equal.

Theorem 2.6.1 immediately implies that a non-bipartite projective quadrangulation on n vertices has an odd cycle transversal with at most 1 2 (1 + √ 8n -7) ≈ √ 2n vertices. In order to improve this bound, our initial approach was to consider a centrally symmetric primal-dual midsphere packing of the projective quadrangulation, and then cut it with a random hyperplane (in the spirit of Spielman and Teng [START_REF] Spielman | Disk packings and planar separators[END_REF]), but the bound we obtained with this technique, πn/ √ 3 + O(n2/5 ) ≈ 1.347 √ n, was only slightly better than √ 2n. Along the way, we observed that every 3-connected planar quadrangulation on n vertices has a separator (a set of vertices whose removal divides the graph into pieces of size at most 3n/4) on (1 + o(1))

√ πn ≈ 1.772 n vertices (this has to be compared with the bound of 1.84 n obtained by Spielman and Teng [START_REF] Spielman | Disk packings and planar separators[END_REF], holding for any planar graph on n vertices). We were stuck there until one day, we desperately opened the book [START_REF] Mohar | Graphs on Surfaces[END_REF] at a random page and discovered a theorem of Randby [START_REF] Randby | Minimal embeddings in the projective plane[END_REF] on minimally embedded graphs with a given face-width, and immediately realised that this result has the following simple consequence.

Theorem 2.6.2 ( [START_REF] Esperet | The width of quadrangulations of the projective plane[END_REF]). Let G be a non-bipartite projective quadrangulation on n vertices. Then G has an odd cycle transversal of size at most 1 4 + n - 15 16 .

We also showed that a similar result holds for any 4-vertex-critical 2 graph in which any two odd cycles intersect. We believe that Theorem 2.6.2 is not sharp and that the right bound should be √ n, which would be tight.

Theorem 2.6.3 ([69]

). There are infinitely many values of n for which there are nonbipartite projective quadrangulations on n vertices containing no odd cycle transversal of size less than √ n.

These graphs are depicted in Figure 2.10, for n = 4, 9, 16. Nakamoto and Ozeki [START_REF] Nakamoto | Coloring of locally planar graphs with one color class small[END_REF] have asked whether every n-vertex non-bipartite projective quadrangulation can be 4-colored so that one color class has size 1 and another has size o(n). While we were unable to answer their question in general, we gave a positive answer when the maximum degree is o(n).

Theorem 2. 6.4 ([69]). Let G be a non-bipartite projective quadrangulation on n vertices, with maximum degree ∆. There exists an odd cycle transversal of size at most √ 2∆n inducing a single edge.

It was proved by Tardif [183] that the generalised Mycielski graphs have fractional chromatic number 2 + o( 1n ), so a natural question is whether the same holds for projective quadrangulations of large edge-width. Note that it was proved by Goddyn [START_REF] Goddyn | Circular chromatic number of even-faced projective plane graphs[END_REF] (see also [START_REF] Devos | Coloring-flow duality of embedded graphs[END_REF]), in the same spirit as the result of Youngs [START_REF] Youngs | 4-chromatic projective graphs[END_REF] on the chromatic number, that the circular chromatic number of a projective quadrangulation is either 2 or 4. We omit the definition of circular coloring here, but we will meet this notion again in Chapter 4.

Equitable arboricity

An equitable partition of a graph G is a partition of the vertex-set of G such that the sizes of any two parts differ by at most one. Hajnal and Szemerédi [START_REF] Hajnal | Proof of a conjecture of P. Erdős[END_REF] proved the following result, which was conjectured by Erdős (see also [START_REF] Kierstead | A fast algorithm of equitable coloring[END_REF] for a shorter proof).

Theorem 2.6.5 ([92]). For any integers ∆ and k ∆ + 1, any graph with maximum degree ∆ has an equitable partition into k stable sets.

Note that there is no constant c, such that for any k c, any star can be equitably partitioned into k stable sets. Wu, Zhang and Li [START_REF] Wu | Equitable vertex arboricity of graphs[END_REF] made the following two conjectures.

Conjecture 2.6.6 ([200]

). There is a constant c such that for any k c, any planar graph can be equitably partitioned into k induced forests. , any graph of maximum degree ∆ can be equitably partitioned into k induced forests.

With Lemoine and Maffray [START_REF] Esperet | Equitable partition of graphs into induced forests[END_REF], we gave two simple proofs of Conjecture 2.6.6.

A proper coloring of a graph G is acyclic if any cycle of G contains at least 3 colors. We first proved the following result (we include the very short and simple proof). Theorem 2.6.8 ( [START_REF] Esperet | Equitable partition of graphs into induced forests[END_REF]). Let k 2. If a graph G has an acyclic coloring with at most k colors, then G can be equitably partitioned into k -1 induced forests.

Proof. The proof proceeds by induction on k 2. If k = 2 then G itself is a forest and the result trivially holds, so we can assume that k 3. Let V 1 , . . . , V k be the color classes in some acyclic k-coloring of G (note that some sets V i might be empty).

Let n be the number of vertices of G. Without loss of generality, we can assume that V 1 contains at most n k n k-1 vertices. Observe that the sum of the number of vertices in

V 1 ∪ V i , 2 i k, is n + (k -2)|V 1 | n. It follows that there exists a color class, say V 2 , such that V 1 ∪ V 2 contains at least n k-1 vertices. Let S be a set of vertices of G consisting of V 1 together with n k-1 -|V 1 | vertices of V 2
, and let H be the graph obtained from G by removing the vertices of S. Note that S induces a forest in G, and H has an acyclic coloring with at most k -1 colors (with color classes V 2 \ S, V 3 , . . . , V k ). By the induction hypothesis, H has an equitable partition into k -2 induced forests, and therefore G has an equitable partition into k -1 induced forests.

It was proved by Borodin [14] that any planar graph has an acyclic coloring with at most 5 colors. Therefore, Theorem 2.6.8 implies Corollary 2.6.9, which is a positive answer to Conjecture 2.6.6.

Corollary 2.6.9 ([60]). For any k 4, any planar graph can be equitably partitioned into k induced forests.

The second proof of Conjecture 2.6.6 uses the notion of degeneracy (recall that a graph G is d-degenerate if every subgraph of G contains a vertex of degree at most d). The following was proved by Kostochka, Nakprasit and Pemmaraju [START_REF] Kostochka | On equitable coloring of d-degenerate graphs[END_REF].

Theorem 2.6.10 ( [START_REF] Kostochka | On equitable coloring of d-degenerate graphs[END_REF]). Let k 3 and d 2. Then every d-degenerate graph can be equitably partitioned into k (d -1)-degenerate graphs.

It is not difficult to derive the following result from Theorem 2.6.10. Theorem 2. 6.11 ([60]). For any integers d 1 and k 3 d-1 , any d-degenerate graph can be equitably partitioned into k induced forests.

It follows from Euler's formula that every planar graph is 5-degenerate. Therefore, Theorem 2.6.11 also implies Conjecture 2.6.6 (with c = 81 instead of c = 4 in Corollary 2.6.9).

For a graph G, let χ a (G) denote the least integer k such that G has an acyclic coloring with k colors. It is known that there is a function f such that every graph G is f (χ a (G))-degenerate [START_REF] Dvořák | On forbidden subdivision characterizations of graph classes[END_REF]. However there exist families of 2-degenerate graphs with unbounded acyclic chromatic number. It follows that Theorem 2.6.11 can be applied to wider classes of graphs than Theorem 2.6.8. Since the vertex-set of every planar graph can be partitioned into three induced forests (this follows easily from the fact that planar graphs are 5-degenerate), the following remains open. Conjecture 2.6.12. Every planar graph has an equitable partition into three induced forests.

Partial results on this problem can be found in [START_REF] Zhang | Equitable vertex arboricity of planar graphs[END_REF]. By Theorems 2.6.8 and 2.6.11, a possible counterexample must have acyclic chromatic number equal to 5 and cannot be 2-degenerate.

An interesting question raised by Wollan is whether every K 4 -minor free graph has an equitable partition into two induced forests. This was recently proved by Bonamy, Joos and Wollan (personal communication) while they were waiting for their respective planes at Schipol Airport (Amsterdam, The Netherlands).

Chapter 3 Perfect matchings

In this chapter, we study several problems on perfect matchings in cubic graphs. The Four Color Theorem mentioned in the previous chapter can be equivalently stated as follows: the edge-set of any planar cubic bridgeless graph can be partitioned into 3 perfect matchings. This is not true in general for non-planar cubic bridgeless graphs, as shown by the Petersen graph. However, several fascinating problem regarding coverings of edges of cubic bridgeless graphs by perfect matchings remain open.

We first study the number of perfect matchings in cubic bridgeless graphs, in relation with a conjecture of Lovász and Plummer. We then study a conjecture of Berge and Fulkerson and several of its consequences.

Introduction

A matching in a graph G = (V, E) is a subset of edges M ⊆ E such that each vertex v ∈ V is contained in at most one edge of M . If each vertex is contained in precisely one edge of M , then the matching M is said to be a perfect. Note that if a graph G has a perfect matching, then it contains an even number of vertices.

Observe that in a proper edge-coloring of a graph G, each color class is a matching. Moreover, if G is ∆-regular and has chromatic index ∆, then each color class is a perfect matching. As explained above, a classical reformulation of the Four Color Theorem is that planar cubic bridgeless graphs have chromatic index 3, and therefore the edge-set of any planar cubic bridgeless graph can be partitioned into 3 perfect matchings.

The perfect matching polytope of a graph G = (V, E) is the convex hull of all characteristic vectors of perfect matchings of G. The following sufficient and necessary conditions for a vector w ∈ R E to lie in the perfect matching polytope of G were given by Edmonds [START_REF] Edmonds | Maximum matching and a polyhedron with (0, 1) vertices[END_REF]: E) is a graph, then a vector w ∈ R E lies in the perfect matching polytope of G if and only if the following holds:

Theorem 3.1.1 ([45]). If G = (V,
(1) w is non-negative, (2) for every vertex v of G the sum of the entries of w corresponding to the edges incident with v is equal to one, and

(3) for every set S ⊆ V (G), |S| odd, the sum of the entries corresponding to the edges having exactly one vertex in S is at least one.

For an integer k, we denote by 1 k the vector where all entries are equal to 1 k (in this definition we are purposely vague on the number of entries in the vector, hopefully this number will always be clear from the context). From Theorem 3.1.1, it is not difficult to deduce that for any odd k, and any (k -1)-edge-connected k-regular graph G, the vector 1 k is in the perfect matching polytope of G. In particular, the vector 1 3 is in the perfect matching polytope of every cubic bridgeless graph. This easily implies that for any cubic bridgeless graph G, each edge of G is contained in a perfect matching of G (and therefore each cubic bridgeless graph contains at least 3 perfect matchings), which is a classical result of Petersen [START_REF] Petersen | Die Theorie der regulären graphs[END_REF]. Note that there are cubic graphs that have no perfect matchings (they all contain bridges), see Figure 3.1 for an example. In this chapter we explore two problems related to the fact that the vector 1 3 is in the perfect matching polytope of every cubic bridgeless graph (and thus every cubic bridgeless graph contains at least 3 perfect matchings). The first is a conjecture of Lovász and Plummer stating that each cubic bridgeless graph contains an exponential number of perfect matchings [START_REF] Lovász | Matching theory[END_REF], and the second is a conjecture of Berge and Fulkerson [START_REF] Fulkerson | Blocking and anti-blocking pairs of polyhedra[END_REF], stating that every cubic bridgeless graph G contains 6 perfect matchings (possibly with repetitions) such that each edge of G is contained in precisely two of the 6 perfect matchings.

Many perfect matchings in cubic bridgeless graphs

In the 1970s, Lovász and Plummer conjectured that the number of perfect matchings of a cubic bridgeless graph G should grow exponentially with its order [START_REF] Lovász | Matching theory[END_REF].

Conjecture 3.2.1 (Conjecture 8.1.8 in [START_REF] Lovász | Matching theory[END_REF]). There exists a constant > 0 such that any cubic bridgeless graph G contains at least 2 |V (G)| perfect matchings.

For bipartite graphs, the number of perfect matchings is precisely the permanent of the graph biadjacency matrix. Voorhoeve proved the conjecture for cubic bipartite graphs in 1979 [START_REF] Voorhoeve | A lower bound for the permanents of certain (0, 1)-matrices[END_REF]; Schrijver later extended this result to all regular bipartite graphs [START_REF] Schrijver | Counting 1-factors in regular bipartite graphs[END_REF]. Chudnovsky and Seymour proved the conjecture for all cubic bridgeless planar graphs [START_REF] Chudnovsky | Perfect matchings in planar cubic graphs[END_REF].

For the general case, Edmonds, Lovász and Pulleyblank [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] proved that any cubic bridgeless G contains at least 1 4 |V (G)| + 2 perfect matchings (see also [START_REF] Naddef | Rank of maximum matchings in a graph[END_REF]); this bound was later improved to 1 2 |V (G)| by Král', Sereni and Stiebitz [START_REF] Král | A new lower bound on the number of perfect matchings in cubic graphs[END_REF]. With Král', Škoda, and Škrekovski [START_REF] Esperet | An improved linear bound on the number of perfect matchings in cubic graphs[END_REF], we first improved the bound to 3 4 |V (G)|-10. Then, with Kardoš, and Král', we obtained a superlinear lower bound [START_REF] Esperet | A superlinear bound on the number of perfect matchings in cubic bridgeless graphs[END_REF]. The proofs of the latter bounds use the brick and brace decomposition of matching covered graphs, and its link with the dimension of the perfect matching polytope.

Finally, with Kardoš, King, Král' and Norine [START_REF] Esperet | Exponentially many perfect matchings in cubic graphs[END_REF], we proved the general case of Conjecture 3.2.1.

Theorem 3.2.2 ([57]

). Every cubic bridgeless graph G contains at least 2 |V (G)|/3656 perfect matchings.

Given two perfect matchings M 1 , M 2 of a cubic bridgeless graph G, observe that the symmetric difference M 1 M 2 is a union of even cycles of G.

Theorem 3.2.2 is a direct consequence of the following result.

Theorem 3.2.3 ([57]

). For every cubic bridgeless graph G on n vertices, at least one of the following holds:

(1) Every edge of G is in at least 2 n/3656 perfect matchings, or

(2) G contains two perfect matchings M 1 , M 2 such that M 1 M 2 has at least n/3656 components.

To see that Theorem 3.2.3 implies Theorem 3.2.2, we can clearly assume that (2) holds. Choose two perfect matchings M 1 , M 2 of G such that the set C of components of M 1 M 2 has cardinality at least n/3656, and note that each of these components is an even cycle alternating between M 1 and M 2 . Thus for any subset C ⊆ C, we can construct a perfect matching M C from M 1 by flipping the edges on the cycles in

C , i.e. M C = M 1 C∈C C. The 2 |C| perfect matchings M C are distinct, implying Theorem 3.2.2.
We cannot discard either of the sufficient conditions (1) or (2) in the statement of Theorem 3.2.3. To see that (2) cannot be omitted, consider the graph depicted in Figure 3.2 and observe that each of the four bold edges is contained in a unique perfect matching. To see that (1) cannot be omitted, it is enough to note that there exist cubic graphs with girth logarithmic in their size (see [START_REF] Imrich | Explicit construction of regular graphs without short cycles[END_REF] for a construction). Such graphs cannot have linearly many disjoint cycles, so condition (2) does not hold.

The idea of the proof of Theorem 3.2.3 is as follows. First, as observed above, it follows from Theorem 3.1.1 that the vector 1 3 is in the perfect matching polytope of G, which can be interpreted as the existence of a probability distribution M on the perfect matchings of G such that for every edge e ∈ E(G), Pr[e ∈ M] = 1 3 . If G contains a rather large part that is well-connected, then we can apply a simple reduction similar to that used by Voorhove [START_REF] Voorhoeve | A lower bound for the permanents of certain (0, 1)-matrices[END_REF] in his proof that cubic bipartite graphs have exponentially many perfect matchings. Otherwise, we will be able to identify linearly many disjoints parts S 1 , S 2 , . . . , S 3n/3656 of G with the property that for each i, if we draw a perfect matching at random from M, S i contains an alternating cycle with respect to this perfect matching with probability at least 1 3 (an even cycle C is alternating with respect to a perfect matching M if the edges of C alternate between edges in M and edges not in M ). By linearity of the expectation, this shows that if we draw a perfect matching at random from M, G contains in average at least n/3656 disjoint alternating cycles with respect to this perfect matching. As a consequence, G has two perfect matchings M 1 , M 2 such that M 1 M 2 contains at least n/3656 components, as desired.

It was observed by Seymour that the following result about (k -1)-edge-connected k-regular graphs can easily be deduced from Theorem 3.2.2.

Theorem 3.2.4 ([57]

). Let G be a k-regular (k-1)-edge-connected graph on n vertices for some k 4. Then G contains at least 2 (1-1/k)(1-2/k) n 3656 perfect matchings.

Proof. It follows from Theorem 3.1.1 that there exists a probability distribution M on the perfect matchings of G such that for every edge e ∈ E(G), Pr[e ∈ M] = 1 k . We choose a triple of perfect matchings of G as follows. Let M 1 be an arbitrary perfect matching. We have

E[|M ∩ M 1 |] = n 2k .
Therefore we can choose a perfect matching M 2 so that

|M 2 ∩ M 1 | n 2k . Let Z ⊆ V (G) be the set of vertices not incident with an edge of M 1 ∩ M 2 . Then |Z| (1 -1 k ) n. For each v ∈ Z we have Pr M ∩ δ({v}) ∩ (M 1 ∪ M 2 ) = ∅ = 1 -2 k ,
where δ({v}) denotes the set of edges incident with v. Therefore the expected number of vertices whose three incident edges are in M, M 1 and M 2 respectively, is at least

(1 -1 k )(1 -2 k ) n.
It follows that we can choose a perfect matching

M 3 so that the subgraph G of G with E(G ) = M 1 ∪ M 2 ∪ M 3 has at least (1 -1 k )(1 -2 k
) n vertices of degree three. Let G be obtained from G by deleting vertices of degree one and replacing by an edge every maximal path in which all the internal vertices have degree two. The graph G is cubic and bridgeless and therefore by Theorem 3.2.2, G (and therefore also G and G) have at least 2

1 3656 |V (G )| 2 (1-1/k)(1-2/k
) n 3656 perfect matchings, as desired.

The Berge-Fulkerson conjecture

Recall that it follows from Theorem 3.1.1 that the vector 13 is in the perfect matching polytope of any cubic bridgeless graph. A famous conjecture of Berge and Fulkerson [START_REF] Fulkerson | Blocking and anti-blocking pairs of polyhedra[END_REF] from the 1970s states that the edge-set of every cubic bridgeless graph can be covered by 6 perfect matchings, such that each edge is covered precisely twice. This can be restated as: for any cubic bridgeless graph G, the vector 1 3 can be expressed as a convex combination of at most 6 perfect matchings of G. Another equivalent statement is in terms of graph coloring: any cubic bridgeless graph has a proper coloring of its edges with 6 colors, such that each edge is assigned precisely two colors. Note that cubic graphs with chromatic index 3 (in particular, planar cubic bridgeless graphs) trivially satisfy the Berge-Fulkerson conjecture.

Not only is this conjecture wide-open, but several weaker versions are also open. One of them is the following conjecture of Fan and Raspaud [START_REF] Fan | Fulkerson's conjecture and circuit covers[END_REF]. Conjecture 3.3.1 ([71]). If G is a cubic bridgeless graph, then there exist three perfect matchings

M 1 , M 2 and M 3 of G such that M 1 ∩ M 2 ∩ M 3 = ∅.
A natural middle step between the Berge-Fulkerson and the Fan-Raspaud conjecture is the following (which is of course also open).

Conjecture 3.3.2. If G is a cubic bridgeless graph, then there exist four perfect matchings such that any three of them have empty intersection.

For a cubic bridgeless graph G, let m(G) be the minimum number of perfect matchings of G whose union covers the edge-set of G. This parameter is sometimes called the excessive index of G. Berge conjectured that for any cubic bridgeless graph G, m(G) 5 (which would be a simple consequence of the Berge-Fulkerson conjecture). It was proved by Mazzuoccolo [139] that this conjecture is indeed equivalent to the Berge-Fulkerson conjecture. It is still not known if there is a constant k such m(G) k for any cubic bridgeless graph G.

Note that a cubic bridgeless graph G satisfies m(G) 3 if and only if it is 3-edge-colorable, and deciding the latter is NP-complete. Hägglund [START_REF] Hägglund | On snarks that are far from being 3-edge colorable[END_REF]Problem 3] asked if it is possible to give a characterization of all cubic graphs G with m(G) = 5. With Mazzuoccolo [START_REF] Esperet | On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings[END_REF], we proved that the structure of cubic bridgeless graphs G with m(G) 5 is far from trivial. More precisely, we showed that deciding whether a cubic bridgeless graph G satisfies m(G) 4 (resp. m(G) = 4) is NP-complete.

The gadgets used in the proof of NP-completeness have many 2-edge-cuts, so our result does not say much about 3-edge-connected cubic graphs. A snark is a non 3-edge-colorable cubic graph with girth at least five that is cyclically 4-edgeconnected 1 (snarks will be studied in more details in Chapter 4). A question raised by Fouquet and Vanherpe [START_REF] Fouquet | On the perfect matching index of bridgeless cubic graphs[END_REF] is whether the Petersen graph is the only snark with excessive index at least five. This question was answered by the negative by Hägglund using a computer program [START_REF] Hägglund | On snarks that are far from being 3-edge colorable[END_REF]. He proved that the smallest snark distinct from the Petersen graph having excessive index at least five is a graph on 34 vertices. With Mazzuoccolo [START_REF] Esperet | On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings[END_REF], we proved that the graph found by Hägglund is a special member of an infinite family F of snarks with excessive index precisely five. These graphs can be constructed inductively from smaller graphs in the class (starting from the Petersen graph). The construction is sketched in Figure 3.3. More precisely we proved that if G 0 , G 1 , G 2 are snarks with excessive index at least 5, then so is the graph G (in Figure 3.3, right). Note that the counterexample of Hägglund was later generalized in a different direction by Abreu, Kaiser, Labbate and Mazzuoccolo [START_REF] Abreu | Treelike snarks[END_REF], and more recently by Máčajová and Škoviera [START_REF] Máčajová | Cubic graphs that cannot be covered with four perfect matchings[END_REF].

G 1 G 2 G 0 G Figure 3.3: The construction of G (right) from G 0 , G 1 , and G 2 .
It turns out that our family F also has interesting properties with respect to short cycle covers. A cycle cover of a graph G is a covering of the edge-set of G by cycles, (i.e. each edge is in at least one cycle of the cycle cover). The length of a cycle cover is the sum of the number of edges in each cycle. The Shortest Cycle Cover Conjecture of Alon and Tarsi [START_REF] Alon | Covering multigraphs by simple circuits[END_REF] states that every bridgeless graph G has a cycle cover of length at most 7 5 |E(G)|. This conjecture implies a famous conjecture due to Seymour [START_REF] Seymour | Sums of circuits[END_REF] and Szekeres [START_REF] Szekeres | Polyhedral decompositions of cubic graphs[END_REF], the Cycle Double Cover Conjecture, which asserts that every bridgeless graph has a cycle cover such that every edge is covered precisely twice (see [START_REF] Jamshy | Shortest cycle covers and the cycle double cover conjecture[END_REF]). It turns out that the Cycle Double Cover Conjecture also has interesting connections with the excessive index of snarks. Indeed, it was proved independently by Steffen [START_REF] Steffen | 1-factor and cycle covers of cubic graphs[END_REF] and Hou, Lai, and Zhang [START_REF] Hou | On perfect matching coverings and even subgraph coverings[END_REF] that it is enough to prove the Cycle Double Cover conjecture for snarks with excessive index at least five.

The best known upper bound on the length of a cycle cover of a bridgeless graph G, 5 3 |E(G)|, was obtained by Alon and Tarsi [START_REF] Alon | Covering multigraphs by simple circuits[END_REF] and Bermond, Jackson and Jaeger [START_REF] Bermond | Shortest coverings of graphs with cycles[END_REF]. For cubic bridgeless graphs there is a trivial lower bound of 4 3 |E(G)|, which is tight for 3-edge-colorable cubic graphs. In the case of cubic bridgeless graphs, Jackson [START_REF] Jackson | Shortest circuit covers of cubic graphs[END_REF] proved an upper bound of 64 39 |E(G)|, and Fan [START_REF] Fan | Shortest cycle covers of cubic graphs[END_REF] improved it to 44 27 |E(G)|. The best known bound, 34 21 |E(G)|, was obtained by Kaiser, Král', Lidický, Nejedlý and Šámal [START_REF] Kaiser | Short cycle covers of cubic graphs and graphs with minimum degree three[END_REF] in 2010.

Brinkmann, Goedgebeur, Hägglund and Markström [START_REF] Brinkmann | Generation and properties of snarks[END_REF] proved using a computer program that the only snarks G on m edges and at most 36 vertices having no cycle cover of length 4 3 m are the Petersen graph and the 34-vertex graph of Hägglund mentioned above. Moreover, these two graphs have a cycle cover of length 4 3 m + 1. They also conjectured that every snark G has a cycle cover of size at most ( 43 + o(1))|E(G)|. With Mazzuoccolo [START_REF] Esperet | On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings[END_REF], we showed that all the graphs G in our infinite family F have shortest cycle cover of length more than 4 3 |E(G)|. We also found the first known snark with no cycle cover of length less than 4 3 |E(G)| + 2 (this graph on 106 vertices is depicted in Figure 3.4). We now turn to a slightly different problem in connection with the Berge-Fulkerson conjecture. Let m k (G) be the maximum fraction of edges in G that can be covered by k perfect matchings and let m k be the infimum of m k (G) over all cubic bridgeless graphs G. As mentioned above, the Berge-Fulkerson conjecture is equivalent to m 5 = 1 and it is not known if there exist a constant k such that m k = 1.

As a nice application of Theorem 3.1.1, Kaiser, Král' and Norine [START_REF] Kaiser | Unions of perfect matching in cubic graphs[END_REF] proved that the infimum m 2 is a minimum, attained by the Petersen graph (i.e. m 2 = 3 5 ), and Patel [START_REF] Patel | Unions of perfect matchings in cubic graphs and implications of the Berge-Fulkerson Conjecture[END_REF] conjectured that the values of m 3 and m 4 are also attained by the Petersen graph. In other words: Conjecture 3. 3.3 ([163]). m 3 = 4 5 . Conjecture 3. 3.4 ([163]). m 4 = 14 15 . Patel proved [START_REF] Patel | Unions of perfect matchings in cubic graphs and implications of the Berge-Fulkerson Conjecture[END_REF] that the Berge-Fulkerson conjecture implies Conjectures 3.3.3 and 3.3.4, while Tang, Zhang and Zhu [START_REF] Tang | Perfect Matching Covering, the Berge-Fulkerson Conjecture and the Fan-Raspaud Conjecture[END_REF] showed that fractional versions of Conjectures 3.3.3 and 3.3.4 imply the Fan-Raspaud conjecture: for instance, they proved that if for any cubic bridgeless graph G and any edge-weighting of G, a weighted version of m 3 (G) is at least 4 5 , then the Fan-Raspaud conjecture holds. With Mazzuoccolo [START_REF] Esperet | On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph[END_REF], we showed that it is enough to consider only the edgeweighting where every edge has weight 1. More precisely, we showed that m 4 = 14 15 implies Conjecture 3.3.2 and m 3 = 4 5 implies the Fan-Raspaud conjecture. We also showed that m 4 = 14 15 implies m 3 = 4 5 . We summarize the implications between these conjectures in Figure 3.5.

Tang, Zhang and Zhu [START_REF] Tang | Perfect Matching Covering, the Berge-Fulkerson Conjecture and the Fan-Raspaud Conjecture[END_REF] conjectured that for any real 4 5 < τ 1, determining whether a cubic bridgeless graph G satisfies m 3 (G) τ is an NP-complete problem. With Mazzuoccolo [START_REF] Esperet | On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph[END_REF], we proved this conjecture together with similar statements for m 2 (G) and m 4 (G). Using arguments similar to that of [START_REF] Kaiser | Unions of perfect matching in cubic graphs[END_REF], it can be proved that any graph G ∈ F 3/5 has a set M of at least three perfect matchings, such that for any M ∈ M there is a set M M of at least three perfect matchings of G satisfying the following: for any M ∈ M M , |M ∪ M | = 3 5 |E(G)|. However, this necessary condition is not sufficient: it is not difficult to show that it is satisfied by the dodecahedron and by certain families of snarks.

An interesting question is whether there exists any 3-edge-connected cubic bridgeless graph G ∈ F 3/5 that is different from the Petersen graph. Similarly, we do not know if it can be decided in polynomial time whether a cubic bridgeless graph G satisfies m 3 (G) = 4 5 (resp. m 4 (G) = 14 15 ), but the questions seem to be significantly harder than for m 2 (since it is not known whether m 3 = 4 5 and m 4 = 14 15 ).

Chapter 4

Nowhere-zero flows

This chapter is devoted to the study of flows and orientations in graphs (in particular in cubic graphs). Nowhere-zero flows are a natural object that is in duality with graph colorings for planar graphs. For cubic graphs, which have been studied in the previous chapter, there is also a natural connexion with perfect matchings, since a cubic graph has a nowhere-zero 4-flow (a flow with values 1, 2, 3) if and only if it is 3-edge-colorable (i.e. its edge-set can be partitioned into 3 perfect matchings). We first study a conjecture of Jaeger, Linial, Payan and Tarsi on additive bases in vector spaces, in connection with conjectures of Tutte and Jaeger on flows and orientations in highly edge-connected graphs. We then investigate problems related to circular flows in cubic graphs, and in particular in snarks.

Introduction

All the graphs considered in this chapter are loopless multigraphs. For more details on flows and any notion not defined here, the reader is referred to [START_REF] Zhang | Integer Flows and Cycle Covers of Graphs[END_REF].

Let G = (V, E) be a graph. Recall that an orientation G = (V, E) of G is obtained by giving each edge of E one of the two possible directions. For each edge e ∈ E, we denote the corresponding arc of E by e, and vice versa. Recall that for a vertex v ∈ V , we denote by δ + G (v) the set of arcs of E leaving v, and by δ - G (v) the set of arcs of E entering v.

For an integer k, a k-flow in an oriented graph G

= (V, E) is a mapping f : E ↔ ±{0, 1, 2, . . . , k -1} such that for any vertex v, ∂f (v) = 0, where ∂f (v) = e∈δ + G (v) f (e) -e∈δ - G (v) f (e). If 0 ∈ f ( E), the flow f is said to be a nowhere-zero k-flow.
Observe that if an oriented graph G has a nowhere-zero k-flow, then the oriented graph obtained from G by reversing the orientation of an arc also has a nowhere-zero k-flow. Therefore, having a nowhere-zero k-flow is merely a property of the underlying non-oriented graph, and does not depend of the chosen orientation: we say that a graph G has a nowhere-zero k-flow if some orientation of G has a nowhere-zero k-flow (equivalently, if any orientation of G has a nowhere-zero k-flow). For a graph G, the smallest integer k such that G has a nowhere-zero k-flow is called the flow number of G, denoted by φ(G). If no such integer k exists, we set φ(G) = ∞.

For a plane graph G, the dual graph of G, denoted by G * , is the graph whose set of vertices is the set of faces of G, and such that two vertices of G * are adjacent if and only if the two corresponding faces of G share an edge. Tutte [START_REF] Tutte | A Contribution on the Theory of Chromatic Polynomial[END_REF] proved the following result, showing the connection between flows and colorings in planar graphs. The following two conjectures are due to Tutte. The first one (see [START_REF] Steinberg | Grötzsch's Theorem dualized[END_REF] and [START_REF] Bondy | Graph Theory with Applications[END_REF]) can be seen as a dual of a classical result of Grötzsch [START_REF] Grötzsch | Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF], which states that triangle-free planar graphs are 3-colorable (this result was mentioned several times in Chapter 2). By Theorem 4.1.1 and the Four color theorem, every 2-edge-connected planar graph has a nowhere-zero 4-flow. However, some 2-edge-connected graphs do not admit nowhere-zero 4-flows (the Petersen graph is the smallest such example). Tutte conjectured the following.

Conjecture 4. 1.3 ([190]). Every 2-edge-connected graph has a nowhere-zero 5-flow.

Since all that is needed to define a flow is a notion of addition and subtraction (with commutativity), we can as well consider that the flow values are in some (additive) abelian group (A, +): an A-flow in G is a mapping f : E → A such that ∂f (v) = 0 for every vertex v, where all operations are performed in A. As before, an A-flow f in G = (V, E) is a nowhere-zero A-flow if 0 ∈ f ( E), i.e. each arc of G is assigned a non-zero element of A. Again, we also say that a non-oriented graph G has a nowhere-zero A-flow if some orientation (and equivalently, any orientation) of G has a nowhere-zero A-flow.

A classical result of Tutte [START_REF] Tutte | A Contribution on the Theory of Chromatic Polynomial[END_REF] states that for any abelian group A, a graph G has a nowhere-zero A-flow if and only if G has a nowhere-zero k-flow, where k denotes the cardinality of A. Let Z k denote the additive group of integers modulo k. In particular, a graph has a nowhere-zero k-flow if any only if it has a nowhere-zero Z k -flow, and a graph has a nowhere-zero 2 k -flow if any only if it has a nowhere-zero Z k 2 -flow. It is not difficult to deduce from this remark that a graph has a nowhere-zero 2 k -flow if and only if its edge-set can be covered by k Eulerian subgraphs (subgraphs in which all the vertices have even degree). Jaeger [START_REF] Jaeger | Flows and generalized coloring theorems in graphs[END_REF] used this observation to prove that every 4-edge-connected graph has a nowhere-zero 4-flow, and every 2-edge-connected graph has a nowhere-zero 8-flow. Later, Seymour proved that every 2-edge-connected graph admits a nowhere-zero Z 2 × Z 3 -flow, and thus a nowhere-zero 6-flow [START_REF] Seymour | Nowhere-zero 6-flows[END_REF]. These were the strongest results (in terms of integer flows) on Conjectures 4.1.2 and 4.1.3 until quite recently.

Since the existence of a nowhere-zero 3-flow is equivalent to the existence of a nowhere-zero Z 3 -flow, it is not difficult to check that Conjecture 4.1.2 is equivalent to the fact that every 4-edge-connected graph has an orientation in which the outand in-degree of each vertex are equal modulo 3. Jaeger conjectured the following more general statement in 1988 [START_REF] Jaeger | Nowhere-zero flow problems[END_REF]. For k 2, a Z k -orientation of a graph G is an orientation such that for each vertex v of G, d As observed above, this conjecture is equivalent to Conjecture 4.1.2 for k = 1. It also implies Conjecture 4.1.3 for k = 2. Restricted to planar graphs, Jaeger's conjecture is equivalent to the fact that for any k 1, every planar graph of girth at least 4k has a homomorphism to C 2k+1 , or equivalently, has circular chromatic number at most 2 + 1 k (circular coloring will be defined in Section 4.3). In the same vein as in Theorem 2.5.24, we proved the following complexity result with Montassier, Ochem and Pinlou [START_REF] Esperet | A complexity dichotomy for the coloring of sparse graphs[END_REF].

+ (v) ≡ d -(v) (mod k).
Theorem 4. 1.5 ([67]). For any k 1, and any t 3, either every t-edge-connected planar graph has a Z 2k+1 -orientation, or deciding whether a t-edge-connected planar graph has a Z 2k+1 -orientation is an NP-complete problem.

In particular, using Theorem 4.2.3 below, we obtain the following more precise result as a corollary.

Corollary 4.1.6. For any k 1, there is an integer 4k t(k) 6k such that every t(k)-edge-connected planar graph has a Z 2k+1 -orientation, while deciding whether a (t(k) + 1)-edge-connected planar graph has a Z 2k+1 -orientation is an NP-complete problem.

We now explore generalizations of Z k -orientations in two directions.

Orientations and flows with boundary

For an integer k 2, a mapping β : k) in G (using the notation introduced in the previous section, this condition can also be phrased as ∂f (v) ≡ β(v) (mod k), where f : E → Z k satisfies f ( e) ≡ 1 (mod k) for any arc e of G). Note that a Z k -orientation is simply a β-orientation where β is defined as β(v) ≡ 0 (mod k) for every vertex v. This conjecture was in turn then generalized by Lai [START_REF] Lai | Mod (2p + 1)-orientations and K 1,2p+1 -decompositions[END_REF], in the same spirit as Conjecture 4.1.4. In a major breakthrough, Thomassen [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] proved that every 8-edge-connected graph has a β-orientation for any Z 3 -boundary β, and every (8k 2 + 10k + 3)-edgeconnected graph has a β-orientation for any Z 2k+1 -boundary β. This was later improved by Lovász, Thomassen, Wu and Zhang [START_REF] Lovász | Nowhere-zero 3-flows and modulo k-orientations[END_REF], as follows. Viewing a Z k -orientation as a Z k -flow in which each arc has flow value 1 (mod k), a natural question is whether Theorem 4.2.3 holds in the more general case where every edge of G starts with some non-zero value in Z k (not necessarily 1).

V → Z k is said to be a Z k -boundary of G if v∈V β(v) ≡ 0 (mod k). Given a Z k -boundary β of G, an orientation G of G is a β-orientation if for any vertex v, d + (v) -d -(v) ≡ β(v) (mod
Given a graph G = (V, E), a Z k -boundary β of G and a mapping f :

E → Z k , an orientation G of G is called an f -weighted β-orientation if ∂f (v) ≡ β(v) (mod k)
for every v. As observed above, if f (e) ≡ 1 (mod k) for every edge e, an f -weighted β-orientation is precisely a β-orientation.

So, can Theorem 4.2.3 be extended to f -weighted β-orientations for any weight? It is not difficult to see that the answer can be negative if 2k + 1 is not a prime number. On the other hand, we proved the following result with de Joannis de Verclos, Le and Thomassé [START_REF] Esperet | Additive bases and flows in graphs[END_REF]. In fact, both results are simple consequences of a more general result on additive bases in vector spaces, as we now explain. An additive basis B of a vector space F is a multiset of elements from F such that for all β ∈ F , there is a subset of B which sums to β. Let Z n p be the n-dimensional linear space over the prime field Z p . Given a collection of sets X 1 , ..., X k , we denote by k i=1 X i the union with repetitions of X 1 , ..., X k . Jaeger, Linial, Payan and Tarsi [START_REF] Jaeger | Group connectivity of graphs -A non homomogeneous analogue of nowhere-zero flow properties[END_REF] We now give a brief overview of the proof of Theorem 4.2.7. We first prove that we can assume that there cannot be too many vectors of support of size 1 (and thus that these vectors can be left aside completely). Then we construct an n-vertex multigraph G out of our family of vectors in a natural way (each vector corresponds to an edge of G connecting the indices of the two non-zero entries of the vector). Since there are few possible multisets of two entries in Z p \ {0}, one of them has to appear on a large fraction of the edges, so the corresponding subgraph H of G has large average degree. Using a classical result of Mader, we can find a highly edge-connected part X of H and then do two things: (1) contract the entries corresponding to X in the family of vectors, and apply induction and ( 2) apply (a variant of) Theorem 4.2.3 to X to complete the proof. Thus, all the results mentioned above, which extend Theorem 4.2.3, are themselves applications of Theorem 4.2.3.

In the linear subspace (Z n p ) 0 of vectors of Z n p whose entries sum to 0 (mod p), the bound on the number of linear bases can be slightly improved. Theorem 4.2.8 ([55]). Let p 3 be a prime number. For any t 4(p -1)(3p -4) + p -2 linear bases B 1 , ..., B t of (Z n p ) 0 such that the support of each vector has size at most 2, t s=1 B s forms an additive basis of (Z n p ) 0 .

To deduce Theorem 4.2.4 from Theorem 4.2.8, consider a highly edge-connected graph G and fix some arbitrary orientation G = (V, E) of G. We denote the vertices of G by v 1 , . . . , v n , and the number of edges of G by m. For each arc e = (v i , v j ) of G, we associate to e a vector x e ∈ (Z n p ) 0 in which the i th -entry is equal to f (e) (mod p), the j th -entry is equal to -f (e) (mod p) and all the remaining entries are equal to 0 (mod p).

Let us consider the following statements.

(a) For each Z p -boundary β, there is an f -weighted β-orientation of G.

(b) For each Z p -boundary β there is a vector (a e ) e∈E ∈ {-1, 1} m , such that e∈E a e x e ≡ β (mod p).

(c) For each Z p -boundary β there is a vector (a e ) e∈E ∈ {0, 1} m such that e∈E 2a e x e ≡ β (mod p).

Clearly, (a) is equivalent to (b). We now claim that (b) is equivalent to (c). To see this, simply do the following for each arc e = (v i , v j ) of G: add f (e) to the j th -entry of x e and to β(v j ), and subtract f (e) from the i th -entry of x e and from β(v i ). It was mentioned to us by one of the referees of [START_REF] Esperet | Additive bases and flows in graphs[END_REF] that similar ideas appear in unpublished lecture notes of Lai and Li [START_REF] Lai | Additive bases and strongly Z 2s+1 -connectedness[END_REF]. To deduce (c) from Theorem 4.2.8, what is left is to show that {a e : e ∈ E} can be decomposed into sufficiently many linear bases of (Z n p ) 0 . This follows from the fact that G is highly edge-connected (and therefore contains many edge-disjoint spanning trees) and that the set of vectors a e corresponding to the edges of a spanning tree of G forms a linear basis of (Z n p ) 0 (see [START_REF] Jaeger | Group connectivity of graphs -A non homomogeneous analogue of nowhere-zero flow properties[END_REF]).

We now give an application of the ideas developed above to antisymmetric flows in highly edge-connected digraphs. For an abelian group (A, +), an A-flow in a digraph G is said to be antisymmetric if the sum of any two (non necessarily distinct) flow values is non-zero. In particular, an antisymmetric flow is also a nowhere-zero flow. Antisymmetric flows were introduced by Nešetřil and Raspaud in [START_REF] Nešetřil | Antisymmetric flows and strong colourings of oriented graphs[END_REF]. A natural obstruction for the existence of an antisymmetric flow in a digraph G is the presence of directed 2-edge-cut in G. Nešetřil and Raspaud asked whether any directed graph without directed 2-edge-cut has an antisymmetric A-flow, for some A. This was proved by DeVos, Johnson and Seymour in [START_REF] Devos | Cut coloring and circuit covering[END_REF], who showed that any directed graph without directed 2-edge-cut has an antisymmetric Z 8 2 × Z 17 3 -flow. It was later proved by DeVos, Nešetřil, and Raspaud [START_REF] Devos | Antisymmetric flows and edgeconnectivity[END_REF], that the group could be replaced by Z 6 2 × Z 9 3 . The best known result is due to Dvořák, Kaiser, Král', and Sereni [START_REF] Dvořák | A note on antisymmetric flows in graphs[END_REF], who showed that any directed graph without directed 2-edge-cut has an antisymmetric Z 3 2 × Z 9 3 -flow (this group has 157464 elements). In the remainder of this section, whenever we talk about a directed k-edgeconnected graph, we mean an orientation of a k-edge-connected graph. Adding a stronger condition on the edge-connectivity allows to prove stronger results on the size of the group A. It was proved by DeVos, Nešetřil, and Raspaud [START_REF] Devos | Antisymmetric flows and edgeconnectivity[END_REF], that every directed 4-edge-connected graph has an antisymmetric Z 2 2 × Z 4 3 -flow, that every directed 5-edge-connected graph has an antisymmetric Z 5 3 -flow, and that every directed 6-edge-connected graph has an antisymmetric Z 2 × Z 2 3 -flow. A natural antisymmetric variant of Tutte's 3-flow conjecture (or rather Jaeger's weak 3-flow conjecture) would be the following: there is a constant k such that every directed k-edge-connected graph has an antisymmetric Z 5 -flow. Note that the size of the group would be best possible, since in Z 2 and Z 2 × Z 2 every element is its own inverse, while an antisymmetric Z 3 -flow or an antisymmetric Z 4 -flow has to assign the same value to all the arcs (and this is impossible in the digraph on two vertices u, v with exactly k arcs directed from u to v, for any integer k ≡ 1 (mod 12)).

The following can easily be deduced from Theorem 4.2.3 using some ideas of the proof of Theorem 4.2.8. Theorem 4.2.9 ( [START_REF] Esperet | Additive bases and flows in graphs[END_REF]). For any k 2, every directed 6k k-1 -edge-connected graph has an antisymmetric Z 2k+1 -flow.

As a corollary, we directly obtain: By duality, using the results of Nešetřil and Raspaud [START_REF] Nešetřil | Antisymmetric flows and strong colourings of oriented graphs[END_REF], Corollary 4.2.10 directly implies that every orientation of a planar graph of girth at least 12 has a homomorphism to an oriented graph on at most 5 vertices. This was proved by Borodin, Ivanova and Kostochka in 2007 [START_REF] Borodin | Oriented 5-coloring of sparse plane graphs[END_REF], and it is not known whether the same holds for planar graphs of girth at least 11. On the other hand, it was proved by Nešetřil, Raspaud and Sopena [START_REF] Nešetřil | Colorings and girth of oriented planar graphs[END_REF] that there are orientations of some planar graphs of girth at least 7 that have no homomorphism to an oriented graph of at most 5 vertices. By duality again, this implies that there are directed 7-edge-connected graphs with no antisymmetric Z 5 -flow. We conjectured the following: Conjecture 4. 2.11 ([55]). Every directed 8-edge-connected graph has antisymmetric Z 5 -flow.

Circular flows

In this section, we will be mainly interested in the following relaxation of nowherezero flows: for some real r, a circular nowhere-zero r-flow in a graph G is a flow in some orientation of G, such that the flow value on each arc is in [1, r -1]. The circular flow number φ c (G) of a graph G is the infimum of the reals r such that G has a circular nowhere-zero r-flow. If such a value does not exist, we set φ c (G) = ∞. This notion was introduced by Goddyn, Tarsi and Zhang in [START_REF] Goddyn | On (k, d)-colorings and fractional nowhere-zero flows[END_REF], where they proved that the infimum φ c (G) is a minimum, and φ c (G) = φ(G) for any graph G.

An orientation G of a graph G = (V, E) is strong if for any set ∅ = X ⊂ V , δ + (X) 1. It is a classical result that a graph is 2-edge-connected if and only if it has a strong orientation. The following result was proved in [START_REF] Goddyn | On (k, d)-colorings and fractional nowhere-zero flows[END_REF]. where the minimum ranges over all strong orientations G of G.

Goddyn, Tarsi and Zhang in [START_REF] Goddyn | On (k, d)-colorings and fractional nowhere-zero flows[END_REF] also proved that for planar graphs, circular nowhere-zero flows are in duality with circular colorings. For a real number r 1, a circular r-coloring of a graph G = (V, E) is a mapping c from V → [0, r), such that for any edge uv ∈ E, 1 |c(u)c(v)| r -1. The circular chromatic number of G is the infimum real r such that G has a circular r-coloring. As alluded to above, it was proved in [START_REF] Goddyn | On (k, d)-colorings and fractional nowhere-zero flows[END_REF] that for any 2-edge-connected plane graph G, the circular flow number of G is equal to the circular chromatic number of the dual of G.

A consequence of a result of Jaeger [START_REF] Jaeger | Nowhere-zero flow problems[END_REF] is that a graph G has circular flow number at most 2 + 1 k if and only if it has a Z 2k+1 -orientation (this can be seen as the dual version of the fact that a graph has circular chromatic number at most 2 + 1 k if and only if it has a homomorphism to the cycle C 2k+1 ). Let f be a circular nowhere-zero r-flow in some orientation G of a graph G = (V, E). Then for any x ∈ V , both δ + (x), and δ -(x) are non-empty. If G is cubic then V is partitioned into two sets V 1 , V 2 , where V i consists of all vertices of out-degree i in D. A simple counting argument shows that this partition is indeed a bisection, i.e. |V 1 | = |V 2 |. From now on, we view each part of the bisection as a color class (which allows us to talk about monochromatic components, i.e. components that lie completely in one part of the bisection). For some integer k, a bisection (V 1 , V 2 ) of a cubic graph G = (V, E) is a k-weak bisection if every monochromatic component is a tree on at most k -2 vertices.

Assume that there is a monochromatic path xyz in V 1 . Counting the relevant ingoing and outgoing edges, we obtain δ + ({x, y, z}) = 1 and δ -({x, y, z}) = 4, and then it follows from Proposition 4.3.1 that r (4/1) + 1 = 5. If V 1 contains a monochromatic cycle, then all the edges with exactly one endpoint in this cycle are directed toward the cycle in G, which contradicts the fact that G has a circular nowhere-zero r-flow (regardless of the value of r). Since V 1 can clearly be replaced by V 2 , this shows that any cubic graph G with φ c (G) < 5 has a 4-weak bisection. The same degree counting arguments leads to the following more general observation, explicitly stated and proved (for integer values of r) in [START_REF] Jaeger | Balanced Valuations and Flows in Multigraphs[END_REF] : Proposition 4.3.2. If a cubic graph G admits a circular nowhere-zero r-flow, then G has a r -weak bisection.

By Proposition 4.3.2, a direct consequence of Tutte's 5-flow conjecture would be that any cubic bridgeless graph has a 5-weak bisection. The Petersen graph has no 4-weak bisection, so this would be best possible. With Mazzuoccolo and Tarsi [START_REF] Esperet | Flows and bisections in cubic graphs[END_REF], we proved the following stronger result.

Theorem 4. 3.3 ([66]). Every cubic graph admits a 5-weak bisection.

It turns out that proving the result for cubic bridgeless graphs is fairly simple and the major difficulty of the proof comes from bridges. It had been suggested by Ban and Linial [START_REF] Ban | Internal Partitions of Regular Graphs[END_REF] that every cubic graph, other than the Petersen graph, admits a 4-weak bisection (i.e. every monochromatic component is either an isolated vertex or a single edge). With Mazzuoccolo and Tarsi [START_REF] Esperet | Flows and bisections in cubic graphs[END_REF], we constructed an infinite family of cubic graphs with no 4-weak-bisections (the construction is depicted in Also, it is not difficult to find a bipartition (V 1 , V 2 ) of the vertex-set of the Petersen graph such that each monochromatic component contains at most 2 vertices, and such that |V 1 | and |V 2 | differ by at most two, so the following might very well be true. As a result of Proposition 4.3.2, every cubic graph G with 4 φ c (G) < 5 admits a 4-weak bisection. Accordingly, a counterexample for Conjecture 4.3.4 should be looked for among cubic graphs G with φ c (G) 5. Constructing such graphs with 2and 3-edge-cuts (starting from the Petersen graph) is fairly easy, but finding examples of higher connectivity is a more difficult task. A snark is a cyclically 4-edge-connected cubic graph of girth at least 5, with no 3-edge-coloring (equivalently, with no circular nowhere-zero 4-flow). Because a snark is well-connected, one might expect that it has circular flow number less than 5. The Petersen graph shows that it is not the case, however it was conjectured by Mohar in 2003 that it is the only counterexample [START_REF] Mohar | Problem of the Month[END_REF]. The conjecture was refuted in 2006 by Máčajová and Raspaud [START_REF] Máčajová | On the Strong Circular 5-Flow Conjecture[END_REF], who constructed an infinite family of snarks with circular flow number 5.

With Mazzuoccolo and Tarsi [START_REF] Esperet | Flows and bisections in cubic graphs[END_REF], we found a more systematic way to generate snarks with circular flow number at least 5. The building blocks of our constructions are 2-terminal networks such that the set of possible flow values that can be transferred from one terminal to the other (this set of flow values is called the capacity of the network) is fairly restricted. These networks can be inductively obtained from smaller networks, starting with a single edge or the Petersen graph minus an edge, using series and parallel constructions. Similar ideas were used by Pan and Zhu [START_REF] Pan | Construction of Graphs with Given Circular Flow Numbers[END_REF] to construct, for any real number 4 < r < 5, infinitely many snarks G with φ c (G) r. The capacity of the serial join of two networks is the intersection of the two capacities, while the capacity of the parallel join of two networks is the sum of the two capacities (here, the sum of two sets A and B is defined as {a + b | a ∈ A, b ∈ B}). These building blocks are then arranged in various ways to produce highly edge-connected graphs with circular flow number at least 5 (see Figure 4.2, left), and the vertices of degree greater than 3 are then expanded in various ways to obtain snarks with circular flow number at least 5 (see We were able to use the versatility of our construction techniques to prove the following complexity result. Theorem 4. 3.6 ([66]). For every rational 4 < r 5, deciding whether an input snark G, satisfies φ c (G) < r is an NP-complete problem.

In particular, deciding whether an input snark G, satisfies φ c (G) < 5 is an NPcomplete problem. This is in contrast with the fact that prior to 2006, the Petersen graph was the only known snark with circular flow number at least 5. It turns out that our proof gives an inapproximability result rather than a simple NP-completeness result (using the fact that we use few different gadgets and everything has to be rational): with a more careful analysis, we can show that for any < 1 13 , given a snark G with circular flow number less than 5or at least 5, deciding whether φ c (G) < 5or φ c (G) 5 is an NP-complete problem. Hence, the circular flow number of snarks cannot be approximated within a factor of 5/(5 -1 13 ) = 65 64 (unless P=NP).

  |E(H)|/|V (H)|, over all shallow topological minors H of G at depth d. Note that ∇ 0 (G) = mad(G)/2 and the function d → ∇ d (G) is monotone increasing. If there is a function f such that for every d 0, every graph G ∈ F satisfies ∇ d (G) f (d), then F is said to have bounded expansion.

Figure 2 . 1 :

 21 Figure 2.1: Two constructions allowing to derive Theorem 2.3.1 from Theorem 2.2.3.

Figure 2 1 Figure 2 . 3 :

 2123 Figure 2.3: Two simple k-touching families of Jordan regions with chromatic number k + 1.

Figure 2 . 4 :

 24 Figure 2.4: Turning a one-sided contact system of strings into a simple touching family of Jordan regions.

Figure 2 . 5 :

 25 Figure 2.5: The construction of a 2 -sun (left), and a set S of k-touching strings requiring 9 2 (k -1) distinct colors (each dashed circle represents a 2 -sun) (right).

Theorem 2 .

 2 3.11 ([23]). For any planar directed graph G, ν * (G) 15.95 • ν(G).

Figure 2 . 6 :

 26 Figure 2.6: Some small counterexamples to Scott's conjecture.

Figure 2 . 7 :

 27 Figure 2.7: A 5-chromatic P 5 -free graph with no K 4 .

Conjecture 2 . 3 . 19 .

 2319 For any hereditary χ-bounded class C of graphs, there is a constant c such that for any graph G ∈ C, χ(G) ω(G) c .

Figure 2 . 8 :

 28 Figure 2.8: The graphs U 3 (left) and Q 5 (right).

  Given a plane graph G, we denote by O(G) the set of vertices of G lying on the outerface of G. Theorem 2.5.2 is a direct consequence of the following technical result. Theorem 2.5.3 ([56]). Every plane graph G with maximum degree ∆ 1 can be 3-colored in such a way that (i) each monochromatic component has size at most (15∆) 32∆+8 ; (ii) only colors 1 and 2 are used for vertices on O(G); and (iii) each component of color 1 intersecting O(G) is included in O(G) and has size at most 6 4 ∆ 3 .

Figure 2 . 9 :

 29 Figure 2.9: The Mycielski graph and its embedding as a projective quadrangulation (left and center), and a generalised Mycielski graph (right).

Figure 2 . 10 :

 210 Figure 2.10: The construction of Theorem 2.6.3 for small values of n.

Conjecture 2 . 6 . 7 (

 267 [START_REF] Wu | Equitable vertex arboricity of graphs[END_REF]). For any integers ∆ and k ∆+1 2

Figure 3 . 1 :

 31 Figure 3.1: A cubic graph with no perfect matching.

Figure 3 . 2 :

 32 Figure 3.2: A cubic bridgeless graph in which some edges are in a unique perfect matching.

Figure 3 . 4 :

 34 Figure 3.4: A snark G with with no cycle cover of length less than 4 3 |E(G)| + 2.

Theorem 3 .Figure 3 . 5 :

 335 Figure 3.5: Diagram of implications between various consequences of the Berge-Fulkerson conjecture.

Theorem 4 . 1 . 1 .

 411 For any plane graph G, φ(G) = χ(G * ).

Conjecture 4 . 1 . 2 .

 412 Every 4-edge-connected graph has a nowhere-zero 3-flow.

Conjecture 4 . 1 . 4 (

 414 [START_REF] Jaeger | Nowhere-zero flow problems[END_REF]). For any k 1, any 4k-edge-connected graph has a Z 2k+1 -orientation.

Jaeger, Linial ,

 Linial Payan and Tarsi[START_REF] Jaeger | Group connectivity of graphs -A non homomogeneous analogue of nowhere-zero flow properties[END_REF] conjectured the following variant of Conjecture 4.1.2.

Conjecture 4 . 2 . 1 (

 421 [START_REF] Jaeger | Group connectivity of graphs -A non homomogeneous analogue of nowhere-zero flow properties[END_REF]). For every 5-edge-connected graph G and every Z 3boundary β of G, the graph G has a β-orientation.

Conjecture 4 . 2 . 2 (

 422 [START_REF] Lai | Mod (2p + 1)-orientations and K 1,2p+1 -decompositions[END_REF]). For any k 1, any (4k + 1)-edge-connected graph G, and any Z 2k+1 -boundary β of G, the graph G has a β-orientation.

Theorem 4 . 2 . 3 (

 423 [START_REF] Lovász | Nowhere-zero 3-flows and modulo k-orientations[END_REF]). For any k 1, any 6k-edge-connected graph G, and any Z 2k+1 -boundary β of G, the graph G has a β-orientation.

Theorem 4 .

 4 2.4 ([55]). Let p 3 be a prime number and let G = (V, E) be a (6p -8)(p -1)-edge-connected graph. For any mapping f : E → Z p \ {0} and any Z p -boundary β, G has an f -weighted β-orientation. Theorem 4.2.4 turns out to be equivalent to the following (in the sense that each result can be easily deduced from the other).

Theorem 4 . 2 . 5 (

 425 [START_REF] Esperet | Additive bases and flows in graphs[END_REF]). Let p 3 be a prime number and let G = (V, E) be a directed (6p -8)(p -1)-edge-connected graph. For any arc e ∈ E, let L( e) be a pair of distinct elements of Z p . Then for every Z p -boundary β, G has a Z p -flow f with boundary β such that for any e ∈ E, f ( e) ∈ L( e).

Corollary 4 . 2 .

 42 10 ([55]).

1 .

 1 Every directed 7-edge-connected graph has an antisymmetric Z 15 -flow. 2. Every directed 8-edge-connected graph has an antisymmetric Z 9 -flow. 3. Every directed 9-edge-connected graph has an antisymmetric Z 7 -flow. 4. Every directed 12-edge-connected graph has an antisymmetric Z 5 -flow.

Proposition 4 . 3 . 1 (

 431 [START_REF] Goddyn | On (k, d)-colorings and fractional nowhere-zero flows[END_REF]). For any 2-edge-connected graph G = (V, E), φ c (G) = min

  k≥0

Figure 4 . 1 :

 41 Figure 4.1: A cubic graph with no 4-weak bisection.

Figure 4 . 1 )

 41 . All our examples have bridges, so the following conjecture remains open.

Conjecture 4 .

 4 3.4 ([10]). Every cubic bridgeless graph other than the Petersen graph admits a 4-weak bisection.

Conjecture 4 . 3 . 5 (

 435 [START_REF] Esperet | Flows and bisections in cubic graphs[END_REF]). The vertex-set of any cubic graph can be partitioned into two color classes V 1 and V 2 , satisfying ||V 1 | -|V 2 || 2, such that each monochromatic component contains at most two vertices.

Figure 4 . 2 ,

 42 center and right).

Figure 4 . 2 :

 42 Figure 4.2: A construction of snarks with circular flow number at least 5.

  Observe that if a graph G has a k-coloring in which each monochromatic component contains at most d vertices, then G has a (d -1)-defective coloring with k colors. It follows that coloring problems in the defective setting are usually easier than the coloring problems mentioned in the previous section. A typical example is the result of Edwards, Kang, Kim, Oum and Seymour

1 , d 2 , . . . , d k ) of k integers, we say that a graph G is (d 1 , d 2 , . . . , d k )colorable if each vertex of G can be assigned a color from the set {1, 2, . . . , k} in such a way that for each i ∈ {1, . . . , k}, a vertex colored i has at most d i neighbors colored i. In other words, each color class i induces a subgraph of maximum degree at most d i . Note that a proper coloring is the same as a (0, 0, . . . , 0)-coloring. For an integer d, a (d, d, . . . , d)-coloring is sometimes called a d-improper coloring or d-defective coloring.

  conjectured the following. Conjecture 4.2.6 ([106]). For every prime number p, there is a constant c(p) such that for any t c(p) linear bases B 1 , ..., B t of Z n p , the union t s=1 B s forms an additive basis of Z n p . Alon, Linial and Meshulam [4] proved a weaker version of Conjecture 4.2.6: they showed that the union of any p log n linear bases of Z n p contains an additive basis of Z n p (note that their bound depends on n). The support of a vector x = (x 1 , . . . , x n ) ∈ Z n p is the set of indices i such that x i = 0. With de Joannis de Verclos, Le and Thomassé [55], we proved that Conjecture 4.2.6 holds if the support of each vector has size at most two. Theorem 4.2.7 ([55]). Let p 3 be a prime number. For any t 8 p 2 (3p-4)+p-2 linear bases B 1 , ..., B t of Z n p such that the support of each vector has size at most 2,

t s=1 B s forms an additive basis of Z n p .

In fact, it can even be colored with k colors whenever k 7, using a more recent result of Sanders and Zhao[START_REF] Sanders | Planar graphs of maximum degree seven are class I[END_REF] that is restricted to the class of planar graphs.

A graph G is k-vertex-critical graph if χ(G) = k and for any vertex v of G, χ(G \ v) = k -1.

A graph G = (V, E) is cyclically k-edge-connected if for any bipartition A, B of V such that G[A]and G[B] both contain a cycle, there are at least k edges with one endpoint in A and the other in B.

Part I

Overview of my research activities