La reconnaissance de graphe

 et Lévêque et al. [37].

Le Chapitre 3 est consacré à l'étude de graphes sans trou pair, une classe de graphes proche des graphes parfaits. Plus spécifiquement, nous travaillons sur les graphes sans trou pair et sans étoile d'articualtion. Nous donnons une limite supérieure optimale de son nombre chromatique en termes de nombre de clique et un algorithme en temps polynomial pour les colorer. Ce dernier est, en fait, une conséquence directe de notre preuve que cette classe a rank-width bornée.

Dans le Chapitre 4, nous étudions les graphes sans griffes qui se colorient pour n'importe quel ordre connexe glouton. Ce problème est motivé par le point de vue algorithmique du problème de coloration. L'une des stratégies les plus connues pour colorier un graphe consiste à utiliser un algorithme glouton: on considère un ordre des sommets v 1 , v 2 , . . . , v n du graphe d'entrée et on assigne à v i la plus petite couleur disponible qui n'est pas utilisée par les voisins de v i parmi v 1 , v 2 , . . . , v i-1 (en ajoutant une nouvelle couleur si nécessaire). Le nombre de couleurs que nous utilisons par cet algorithme dépend fortement de l'ordre choisi. Ici nous considérons seulement les ordres connexes, c'est-à-dire où chaque v i a au moins un voisin parmi v 1 , v 2 , . . . , v i-1 . Un graphe G est bon si pour chaque sous-graphe induit connexe H de G, chaque ordre connexe donne H une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits.

Conjecture 2.1.5 (Trotignon 2015 [47]). Every {ISK4, K 3,3 , prism, K 2,2,2 }-free graph contains a vertex of degree at most three.

Conjecture 2. 1.6 (Trotignon, Vušković 2016 [49]). Every {ISK4, K 3,3 , triangle}free graph contains a vertex of degree at most two.

Introduction (in French)

Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Plus formellement, un graphe est une paire ordonnée G = (V, E), où V est un ensemble de sommets (ou noeuds) et E est un ensemble d'arêtes, qui sont des sous-ensembles à 2 éléments de V . Un graphe peut donc être dessiné en spécifiant un ensemble de points et en reliant ces paires qui forment des arêtes. Un exemple de graphe est donné ci-dessous.

Figure 1: Un exemple de graphe Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. Par exemple, un graphe peut être utilisé pour modéliser une carte de transport public, où chaque arrêt est un sommet et deux arrêts conscutifs de la même ligne forment une arête. Un autre exemple est le réseau social, où chaque sommet représente une personne et où il existe une arête entre deux personnes si elles se connaissent. La théorie des graphes implique de répondre à plusieurs problèmes concernant certains graphes spécifiques pour comprendre leur structure, ce qui peut conduire à de nombreuses applications dans la vie réelle. Deux problèmes parmi eux, très célèbres et importants, sont la coloration de graphe et la reconnaissance de graphe (ou la détection de graphe).

INTRODUCTION

La coloration de graphe

Dans le problème de coloration, nous voulons assigner une couleur à chaque sommet telle que deux sommets reçoivent des couleurs différentes s'ils sont connectés par une arête, et le nombre de couleurs que nous utilisons est minimum. Ce problème provient d'une question sur la coloration des cartes, à savoir le problème des quatre couleurs proposée par Guthrie en 1852: supposons que vous ayez une carte divisée en régions, de combien de couleurs avez-vous besoin pour colorer chaque région de telle sorte que deux régions qui partagent une frontière commune ne reçoivent pas la même couleur? Il a conjecturé que quatre couleurs étaient toujours suffisantes. Bien que cette question ait suscité beaucoup d'attention de la part des mathématiciens, elle est restée non résolue jusqu'en 1976, quand Appel et Haken ont finalement donné une preuve. Il est clair que quatre couleurs ne sont jamais assez pour colorer les graphes généraux, et en fait le nombre de couleurs dont nous avons besoin peut être arbitrairement grand (par exemple, un graphe de n sommets tel qu'il y a une arête entre chaque paire d'entre eux, a besoin d'au moins n couleurs). Le problème de coloration des graphes est également difficile en le sens qu'il est NP-difficile (une classe de problèmes où aucun algorithme polynomial n'est connu, et de plus, on soupçonne qu'il n'en existe pas). Par conséquent, on peut se demander s'il existe un algorithme en temps polynomial pour colorer certaines classes de graphes.

En 1960, Berge a défini la classe des graphes parfaits et formulé une autre conjecture sur la coloration des graphes, la Conjecture Forte des Graphes Parfaits, qui concerne une caractérisation des graphes parfaits, initialement motivée par la notion de Shannon de la capacité d'erreur zéro d'un graphe. En 1984, Grötschel, Lovász et Schijver ont montré que des graphes parfaits peuvent être colorés en temps polynomial. Cependant, leur algorithme implique l'utilisation de la méthode des ellipsoïdes, qui n'est pas très efficace et peu pratique. L'existence d'un algorithme purement combinatoire pour colorer des graphes parfaits n'est pas encore connue. Malgré les efforts de nombreux scientifiques, la Conjecture Forte des Graphes Parfaits de Berge sur des graphes parfaits est restée ouverte pendant plus de 40 ans. En 2002, elle a été résolue par Chudnovsky, Robertson, Seymour et Thomas. Elle est maintenant connue comme le Théorème Fort des Graphes Parfaits. Leur preuve est basée sur un théorème de décomposition structurale profond. un algorithme efficace pour reconnaïtre certaines classes de graphes (par exemple, biparti, planaire, parfait, . . . ) ou pour détecter certaines structures spécifiques du graphe d'entrée. Un graphe est un sous-graphe de G s'il peut être obtenu de G en supprimant certains sommets et arêtes. D'un autre côté, un graphe est un sousgraphe induit de G s'il peut être obtenu de G en supprimant certains sommets. Par exemple, pour tout graphe fixe H, on peut vérifier en temps polynomial si un graphe G contient H comme un sous-graphe (induit). La question devient plus difficile si nous demandons si G contient une subdivision de H comme un sous-graphe (induit) (une subdivision de H est obtenue de H en subdivisant ses arêtes, la définition plus formelle est donnée dans le Chapitre 1). La différence entre le sous-graphe et le sousgraphe induit par rapport à cette question est remarquable. Dans les années 1980, le Graph Minor Project de Robertson et Seymour affirmait que pour la notion de sous-graphe, il est toujours possible de trouver un algorithme en temps polynomial. D'autre part, pour la notion de sous-graphe induit, on sait que pour certains graphes H, le problème peut être résolu en temps polynomial et pour d'autres graphes, il devient NP-difficile (voir [START_REF] Lévêque | Detecting induced subgraphs[END_REF] par exemple). De plus, cette dichotomie est encore loin d'être complète. L'étude des graphes parfaits a également conduit à plusieurs questions sur la détection des sous-graphes induits. Suite à la preuve du Théorème Fort des Graphes Parfaits, un algorithme en temps polynomial pour reconnaïtre des graphes parfaits a été découvert par Chudnovsky, Cornuéjols, Liu, Seymour et Vušković. La complexité de la détection de certains types de décomposition et de certaines structures spécifiques utilisées dans la preuve du Théorème Fort des Graphes Parfaits (par exemple, les configurations de Truemper [START_REF] Diot | The (theta, wheel)free graphs Part I: only-prism and only-pyramid graphs[END_REF]) est également considérée.

L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).

La résumé du document

Voyons brièvement le contenu de cette thèse.

Dans le Chapitre 1, nous rappelons quelques notions de base en théorie des graphes, ainsi que certaines structures et décompositions particulières dans le contexte des sous-graphes induits que nous utilisons tout au long de la thèse. Les lecteurs qui connaissent le sujet peuvent passer ce chapitre. Dans chacun des chapitres suivants (du Chapitre 2 au Chapitre 4), nous donnons d'abord une courte introduction du problème et quelques définitions spécifiques qui ne sont utilisées que dans ce chapitre, puis nous montrons la preuve de nos résultats et éventuellement d'autres discussions.

INTRODUCTION

L'objet principal de Chapitre 2 est l'étude des graphes sans ISK4 -les graphes qui ne contiennent aucune subdivision de K 4 en tant que sous-graphe induit. Le premier résultat de ce chapitre est présenté dans la Section 2.1. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment mentionnée dans [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]. Nous donnons aussi une meilleure borne dans le cas sans triangle: le nombre chromatique des graphes sans

Introduction

Graphs are mathematical structures used to model pairwise relations between objects. More formally, a graph is an ordered pair G = (V, E), where V is a set of vertices (or nodes) and E is a set of edges, which are 2-element subsets of V . A graph therefore can be drawn just by specifying a set of points and connecting those pairs which form edges. An example of a graph is given below. Figure 2: An example of a graph Despite their simple structure, graphs have applications in various areas like computer science, physics, biology and sociology. For example, a graph can be used to model a public transport map, where each stop is a vertex and two consecutive stops of the same line form an edge. Another example is the social network, where each vertex represents a person and there exists an edge between two people if they know each other. Graph theory involves answering several problems concerning some specific graphs to understand their structures, which might lead to many real-life applications. Two problems among them which are very famous and important are graph coloring and graph recognition (or graph detection).

Graph coloring

In coloring problem, we would like to assign for each vertex a color such that two vertices receive different colors if they are connected by an edge, and the number 7

INTRODUCTION

of colors that we use is minimum. This problem originates from a question about coloring of maps, namely the Four-Color Conjecture proposed by Guthrie in 1852: suppose that you have a map divided into regions, how many colors do you need to color each region such that no two regions that share a common border receive the same color? He conjectured that four colors were always enough. Although this question attracted a lot of attention from mathematicians, it remained unsolved until 1976, when Appel and Haken finally gave a proof. It is clear that four colors are never enough to color general graphs, and in fact the actual number of colors that we need might be arbitrarily large (for instance, a graph of n vertices such that there is an edge between every pair of them, needs at least n colors). The graph coloring problem is also proved to be difficult in a sense that it is NP-hard (a class of problems where no polynomial-time algorithm is known, and moreover, it is suspected that there does not exist one). Therefore, one might wonder whether there exists a polynomial-time algorithm to color certain graph classes.

In 1960, Berge defined the class of perfect graphs and formulated another conjecture about graph coloring, the Strong Perfect Graph Conjecture, which concerns a characterization of perfect graphs, originally motivated by Shannon's notion of the zero-error capacity of a graph. In 1984, Grötschel, Lovász and Schijver showed that perfect graphs can be colored in polynomial time. However, their algorithm involves the use of ellipsoid method, which is not very efficient and impractical. The existence of a purely combinatorial algorithm to color perfect graphs is still not known. Despite the efforts of many scientists, the Berge

Graph recognition

Second problem that we would like to mention is graph recognition. This is not a particular problem, but a very general concept in graph theory. Basically, we ask whether it is possible to find an efficient algorithm to recognize certain graph classes (e.g. bipartite, planar, perfect,. . . ) or to detect some specific structures of the input graph. A graph is a subgraph of G if it can be obtained from G by deleting some vertices and edges. On the other hand, a graph is an induced subgraph of G if it can be obtained from G by deleting some vertices. For example, for any fixed graph H, one can check in polynomial time whether a graph G contains H as a (induced) subgraph. The question becomes more difficult if we ask if G contains a subdivision of H as a (induced) subgraph (a subdivision of H is obtained from H by subdividing its edges, more formal definition is given in Chapter 1). The difference between subgraph and induced subgraph with respect to this question are remarkable. In the 1980s, the Graph Minor Project by Robertson and Seymour asserted that for subgraph, it is always possible to find a polynomial algorithm. On the other hands, for induced subgraph, we know that for some graphs H, the problem is polynomial-time solvable and for some other graphs, it becomes NPhard (see [START_REF] Lévêque | Detecting induced subgraphs[END_REF] for example). Moreover, this dichotomy is still very far from being complete. The study of perfect graphs also led to several questions on detecting induced subgraphs. Subsequent to the proof of Strong Perfect Graph Theorem, a polynomial algorithm for recognizing perfect graphs was discovered by Chudnovsky, Cornuéjols, Liu, Seymour and Vušković. The complexity of detecting certain kinds of decomposition and some specific structures used in the proof of Strong Perfect Graph Theorem (for example, Truemper configurations [START_REF] Diot | The (theta, wheel)free graphs Part I: only-prism and only-pyramid graphs[END_REF]) is also considered.

The main focus of this thesis is to continue the study of the coloring and detecting problem in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes).

Outline of the document

Let us briefly review the content of this thesis.

In Chapter 1, we recall some basic notions in graph theory, as well as some particular structures and decompositions in the context of induced subgraph that we use throughout the thesis. The readers who are familiar with the subject can skip this chapter. In each of the following chapters (from Chapter 2 to Chapter 4), we first give a short introduction of the problem and some specific definitions that are only used in that chapter, and then we show the proof of our results and possibly some further discussions.

The main object of Chapter 2 is ISK4-free graphs -the graphs that do not contain any subdivision of K 4 as an induced subgraph. The first result of this chapter is presented in the Section 2.1. We prove that the chromatic number of this class is bounded by 24, a big improvement compared to the best known bound which was mentioned in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]. We give also a much better bound in triangle-free case: the chromatic number of (triangle, ISK4)-free graphs is bounded by 4. Note that, right after our results, Chudnovsky et al. [START_REF] Chudnovsky | Triangle-free graphs that do not contain an induced subdivision of K 4 are 3-colorable[END_REF] improve the bound in triangle-free case to 3 by using decomposition technique. However, our proof is much simpler and still gives a nice structural property of the class. In Section 2.2, the second result is presented: we prove that there exists a polynomial-time algorithm for detecting this INTRODUCTION graph class, which answers a question by Chudnovsky et al. [START_REF] Chudnovsky | Detecting an induced net subdivision[END_REF] and Lévêque et al. [START_REF] Lévêque | Detecting induced subgraphs[END_REF].

Chapter 3 is devoted to the study of even-hole-free graphs, a graph class which is close to perfect graphs. More specifically, we work on even-hole-free graphs with no star cutset. We give an optimal upper bound for its chromatic number in terms of clique number and a polynomial-time algorithm to color them. The latter is, in fact, a direct consequence of our proof that this class has bounded rank-width.

In Chapter 4, we study claw-free graphs which are good to color with respect to any greedy connected order. This problem is motivated by algorithmic point of view of coloring problem. One of the most well-known strategy to color a graph is by using a greedy algorithm: we consider an order of the vertices v 1 , v 2 , . . . , v n of the input graph and assign for v i the smallest available color which is not used by v i 's neighbors among v 1 , v 2 , . . . , v i-1 (adding a new color if needed). The number of color we use by this algorithm heavily depends on the chosen order. Here we consider only connected order, an order where each v i has at least a neighbor among v 1 , v 2 , . . . , v i-1 . A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs.

Chapter 1

Basic notions

In the first section of this chapter, we recall some basic notions of graph theory that we use throughout the thesis. Most of them are standard and the reader is referred to [START_REF] Diestel | Graph theory[END_REF] for any undefined terms. In the following sections, we introduce several more specific definitions: the notion of χ-boundedness, some kinds of decomposition and some particular graphs. The readers who are familiar with this field can also skip these sections.

Graphs

A graph G is an ordered pair (V, E) consisting of a vertex (node) set V and an edge set E ⊆ V 2 , where V 2 is the set of all the subsets of size 2 of V . An element {u, v} of E is also denoted by uv or vu. We also refer to V and E as V (G) and E(G), respectively. Two vertices u and v in V (G) such that uv ∈ E(G) are said to be adjacent, and we also say that u is a neighbor of

v. The (open) neighborhood of a vertex v, denoted by N G (v), is the set of neighbors of v. The closed neighborhood of v, denoted by N G [v], is defined as N G (v)∪{v}. The degree of v in G is |N G (v)|. We also extend this notion for a subset X ⊆ V (G) by defining N G (X) := (∪ v∈X N G (v)) \ X and N G [X] := N G (X) ∪ X. We might also write N (v), N [v], N (X), N [X] instead of N G (v), N G [v], N G (X), N G [X]
, respectively, if there is no ambiguity. For some subsets

K ⊆ V (G) and C ⊆ V (G) \ K, we denote by N K (C) the set of neighbors of C in K, or N K (C) := N (C) ∩ K. The complement of G is the graph G = (V, E), where E = V 2 \E.
A clique in G is a set of vertices that are pairwise adjacent. A stable set (or an independent set) in G is a set of vertices that are pairwise non-adjacent. The size of a clique or a stable set is its number of vertices. Let A and B be two disjoint subsets of V (G), we say that A is complete to B if for every u ∈ A and every v ∈ B, uv ∈ E(G). If the set A is of size 1, say A = {u}, we also say that u is complete to B (instead of saying that {u} is complete to B). The complete graph K n is the graph on n vertices that are pairwise adjacent. A graph is called complete bipartite (resp. complete tripartite) if its vertex set can be partitioned into two (resp. three) non-empty stable sets that are pairwise complete to each other. If these two (resp. three) sets have size p, q (resp. p, q, r) then the graph is denoted by K p,q (resp. K p,q,r , see Figure 1 (this is often referred to as induced path or chordless path in literature). We call p 1 and p k the ends of the path P . The interior of P is {p 2 , . . . , p k-1 } and each vertex in the interior of P is said to be an interior (internal ) vertex of P . Let u, v ∈ V (P ), we denote by uP v the subpath of P from u to v and denote by P * the subpath of P from p 2 to p k-1 (i.e. P * := p 2 P p k-1 ). A path P is flat in G if all the interior vertices of P are of degree 2 in G. The length of a path on k vertices is (k -1). A path on k vertices is denoted by P k . A cycle C on k vertices (k ≥ 3) is a graph with vertex set {p 1 , . . . , p k } such that for i, j ∈ {1, . . . , k}, p i is adjacent to p j if |i -j| = 1, where the index is taken modulo k. All the other edges of C (the edges p i p j such that |i -j| > 1) are its chords. A cycle is said to be chordless (or induced ) if it has no chord. The length of a cycle on k vertices is k. A hole is a chordless cycle of length at least 4. A hole of length k is called a k-hole and is denoted by C k . A hole is said to be odd (resp. even) if its length is odd (resp. even). An antihole is the complement of a hole. Note that K 3 is a chordless cycle but it is not a hole. The girth of a graph is the smallest length of its cycle. See Figure 1.3 for an example of paths and holes.

G = (V, E), G = (V , E ). We say that G is isomorphic to G if there exists a bijection φ : V → V such that uv ∈ E ⇐⇒ φ(u)φ(v) ∈ E . Graph G is said to be a subgraph of G if V ⊆ V and E ⊆ E. For some graph H, we say that graph G contains H as a subgraph if there exists X ⊆ V and Y ⊆ E such that (X, Y ) is isomorphic to H. If X ⊆ V , the subgraph of G induced by X, denoted by G[X], is (X, E X ) where E X = {uv|uv ∈ E and u, v ∈ X}. A subgraph G of G is said to be an induced subgraph of G if there exists X ⊆ V such that G = G[X]. For convenience, the subgraph of G induced by V \ X is often denoted by G \ X instead of G[V \ X]. For v ∈ V , we also write G \ v instead of G \ {v}.

Perfect graphs and χ-boundedness

Let us first introduce three graph parameters which play an important role in graph theory. Computing any of them for general graphs is well-known to be NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

• The chromatic number of G, denoted by χ(G), is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices receive the same color (such a coloring is called proper ). Equivalently, one can define the chromatic number of G as the smallest number k such that V (G) can be partitioned into k stable sets. A coloring of G with χ(G) colors is called an optimal coloring of G.

• The clique number of G, denoted by ω(G), is the size of a largest clique in G.

• The stability number (or independence number ) of G, denoted by α(G), is the size of a largest stable set in G.

It is clear that χ(G) ≥ ω(G), since a clique of size k needs at least k different colors in any proper coloring of G. Therefore, clique number gives a natural lower bound for chromatic number. The question is: when does the equality hold? It is clear that the equality does not hold for every graph since a hole of length 5 has ω(C 5 ) = 2, but χ(C 5 ) = 3. In fact, the gap between χ(G) and ω(G) can be arbitrarily large. A triangle is a graph isomorphic to a K 3 . In 1955, Mycielski gave a construction of a family of triangle-free graphs which has large chromatic number [START_REF] Mycielski | Sur le coloriage des graphes[END_REF]. Later, using probabilistic method, Erdős even generalized this result by proving the existence of a graph whose girth and chromatic number are both large [START_REF] Erdős | Graph theory and probability[END_REF].

Perfect graphs are defined in such a way that this equality holds for them. A graph G is perfect if for every induced subgraph H of G, χ(H) = ω(H). In Berge's initial work on perfect graph, he made some nice conjectures on their structure [5]. The most important one, called Strong Perfect Graph Conjecture, was proved by Chudnovsky, Robertson, Seymour and Thomas around 40 years later [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF]. An odd antihole is the complement of an odd hole. The graphs that do not contain an odd hole nor an odd antihole as an induced subgraph are known as Berge graphs.

Theorem 1.2.1 (Strong Perfect Graph Theorem [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF]). A graph is perfect if and only if it is a Berge graph.

The concept of χ-boundedness was introduced by Gyárfás [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF] as a natural extension of perfect graphs: a class of graph G is χ-bounded with χ-bounding function f if, for every graph G ∈ G, χ(G) ≤ f (ω(G)). It is clear that the class of perfect graphs is χ-bounded with the χ-bounding function f (x) = x. Now the question is: which induced subgraphs need to be forbidden to get a χ-bounded class of graphs? The previously mentioned result of Erdős [START_REF] Erdős | Graph theory and probability[END_REF] implies that forbidding only one induced subgraph H may lead to a χ-bounded class only if H has no cycle. Gyárfás conjectured that this is sufficient: Conjecture 1.2.2 (Gyárfás [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]). The class of H-free graphs is χ-bounded if H is a forest.

Another way to obtain a χ-bounded class is to forbid infinite number of graphs. A lot of questions on the χ-boundedness of graph classes defined by forbidding odd holes, even holes, long holes,. . . have been asked [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]. In this thesis, we consider this problem on ISK4-free graphs (see Chapter 2) and even-hole-free graphs with no star cutset (see Chapter 3).

Some kinds of decomposition and graph operations

In this section, we define some kind of decomposition that we use throughout the thesis. Let G = (V, E) be a graph. A cutset in graph G is a subset S V (G) such that G \ S is disconnected.

• For any k ≥ 0, a k-cutset is a cutset of size k.

• The only vertex of a 1-cutset is called the cut-vertex.

• A cutset S is a star cutset if S contains a node x adjacent to every node in S \ x.

• A cutset S is a clique cutset if S is a clique. It is clear that clique cutset is a particular star cutset.

• A proper 2-cutset is a 2-cutset {a, b} such that ab / ∈ E, V (G) \ {a, b} can be partitioned into two non-empty sets X and Y so that there is no edge between X and Y and each of G[X ∪ {a, b}] and G[Y ∪ {a, b}] is not a path from a to b.

The 2-join was first defined by Cornuéjols and Cunningham [START_REF] Cornuéjols | Compositions for perfect graphs[END_REF]. A 2-join in a graph G is a partition (X 1 , X 2 ) of V (G) with specified sets (A 1 , A 2 , B 1 , B 2 ) such that the followings hold:

• |X 1 |, |X 2 | ≥ 3.
• For i = 1, 2, A i ∪ B i ⊆ X i and A i , B i are non-empty and disjoint.

• A 1 is complete to A 2 , B 1 is complte to B 2 and these are the only adjacencies between X 1 and X 2 .

• For i = 1, 2, G[X i ]
contains a path with one end in A i and the other in

B i . Furthermore, G[X i ] is not a path.
In this case, we call (X 1 , X 2 , A 1 , B 1 , A 2 , B 2 ) a split of (X 1 , X 2 ). We also denote by C i the set X i \ (A i ∪ B i ) for i = 1, 2. Note that the first three conditions of a 2-join are standard, while the last one is not. This is often referred to as connected non-path 2-join in literature. This condition varies since it depends on how we want to build our blocks of decompositions with respect to a 2-join. Here we show how to do it with respect to our definition. The blocks of decompositions of G with respect to (X 1 , X 2 ) are the two graphs G 1 , G 2 built as follows. We obtain G 1 by replacing X 2 by a marker path P 2 of length k 2 ≥ 3, from a vertex a 2 complete to A 1 , to a vertex b 2 complete to B 1 (the interior of P 2 has no neighbor in X 1 ). The block G 2 is obtained similarly by replacing X 1 by a marker path P 1 of length k 1 ≥ 3 with two ends a 1 , b 1 .

Note that the way we choose P 1 , P 2 (as well as their lengths) depends on the class we are working with. This definition of a 2-join and this way of constructing blocks of decomposition with respect to a 2-join are consistent throughout this thesis (mainly for Chapter 3).

The next graph operation we introduce is called substitution. Given two graphs

G 1 = (V 1 , E 1 ), G 2 = (V 2 , E 2 ) (V 1 and V 2 are disjoint), and v ∈ V 1 , we say that G is obtained from G 1 by substituting G 2 for v, or G is obtained from G 1 by substituting v by G 2 if: • V (G) = V 1 ∪ V 2 \ {v}. • G[V 2 ] = G 2 . • G[V 1 \ {v}] = G 1 [V 1 \ {v}]. • For every v 1 ∈ V 1 \ {v} and v 2 ∈ V 2 , v 1 v 2 ∈ E(G) if and only if v 1 v ∈ E(G 1 ).

SOME PARTICULAR GRAPHS

Now we present another graph operation named identification. Given two graphs

G 1 = (V 1 , E 1 ), G 2 = (V 2 , E 2 ) (V 1 and V 2 are disjoint) and for some 1 ≤ k ≤ min{|V 1 |, |V 2 |}, let X = {x 1 , . . . , x k } ⊆ V 1 and Y = {y 1 , . . . , y k } ⊆ V 2 be such that x i x j ∈ E 1 if
and only if y i y j ∈ E 2 for every i, j ∈ {1, 2, . . . , k}. We say that G is obtained from G 1 and G 2 by identifying x i with y i for every i ∈ {1, . . . , k} if:

• V (G) = (V 1 \ X) ∪ (V 2 \ Y ) ∪ Z, where Z = {z 1 , . . . , z k }. • G[V 1 \ X] = G 1 [V 1 \ X]. • G[V 2 \ Y ] = G 2 [V 2 \ Y ].
• For every i, j ∈ {1, 2, . . . , k}, z i z j ∈ E(G) if and only if x i x j ∈ E 1 and y i y j ∈ E 2 .

• For every i ∈ {1, . . . , k}:

-For every u ∈ V 1 \ X, z i u ∈ E(G) if and only if x i u ∈ E 1 . -For every u ∈ V 2 \ Y , z i u ∈ E(G) if and only if y i u ∈ E 2 . • There is no edge in G between V 1 \ X and V 2 \ Y .

Some particular graphs

In this section, some particular graphs are presented. Recall that a triangle is a graph isomorphic to a K 3 . A square is a graph isomorphic to a C 4 . A claw is a graph with vertex set {u, x, y, z} and edge set {ux, uy, uz}, vertex u is called the center of that claw (see Figure 1 Let us introduce Truemper configurations. These configurations play an important role in understanding the structure of several classes of objects, such as regular matroids, balanceable matrices and perfect graphs. In decomposition theorem, Truemper configurations appear both as excluded structures that are convenient to work with, and as structures where the actual decomposition takes place. We refer the reader to [START_REF] Vušković | The world of hereditary graph classes viewed through Truemper configurations[END_REF] for a survey on Truemper configurations by Vušković. These configurations include: theta, pyramid, prism and wheel. • Let x, y be two distinct vertices. A theta is a graph induced by three paths from x to y such that any two of them induce a hole (see Figure 1.5a). Note that all these three path are of length greater than 1 by this condition.

• Let x 1 , x 2 , x 3 , y be four distinct vertices such that {x 1 , x 2 , x 3 } induces a triangle. A pyramid is a graph induced by three paths: P 1 from x 1 to y, P 2 from x 2 to y, P 3 from x 3 to y such that any two of them induce a hole (see Figure 1.5b).

A pyramid is long if all three paths are of length greater than 1.

• Let x 1 , x 2 , x 3 , y 1 , y 2 , y 3 be six distinct vertices such that {x 1 , x 2 , x 3 } and {y 1 , y 2 , y 3 } induce two triangles. A prism is a graph induced by three paths: P 1 from x 1 to y 1 , P 2 from x 2 to y 2 , P 3 from x 3 to y 3 such that any two of them induce a hole (see Figure 1.5c). A prism is long if all three paths are of length greater than 1.

• A wheel is a graph consisting of a hole H and a vertex x / ∈ V (H) that has at least three neighbors on H (see Figure 1.5d).

Chapter 2 IKS4-free graphs

An ISK4 is a subdivision of K 4 (K 4 is also an ISK4). A graph is ISK4-free if it does not contain any subdivision of K 4 as an induced subgraph. Series-parallel graphs and line graph of cubic graphs are some examples of ISK4-free graphs (see [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]). The class of ISK4-free graphs has recently been studied. In [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF], a decomposition theorem for this class is given. However, it does not lead to a recognition algorithm. Since the class of ISK4-free graphs contains the line graph of every cubic graph, where finding the edge chromatic number is known to be NP-hard [START_REF] Holyer | The NP-completeness of edge-coloring[END_REF], we know that finding the chromatic number of ISK4-free graphs is also NP-hard. In Section 2.1, we propose new upper bound for the chromatic number of ISK4-free graphs and {ISK4, triangle}-free graphs. In Section 2.2, we give a polynomial-time algorithm for recognizing this class, which answers a question by Chudnovsky et al. [START_REF] Chudnovsky | Detecting an induced net subdivision[END_REF] and Lévêque et al. [START_REF] Lévêque | Detecting induced subgraphs[END_REF]. We also note that the complexity of finding a maximum stable set in ISK4-free graphs remains open. The results of this chapter are covered in the following papers:

[I] N.K. Le. Chromatic number of ISK4-free graphs, Graphs and Combinatorics, 33(6): 1635-1646, 2017.

[II] N.K. Le. Detecting an induced subdivision of K 4 , arXiv preprint, submitted. https://arxiv.org/abs/1703.04637

Chromatic number of ISK4-free graphs 2.1.1 Introduction

We recall the question concerning χ-boundedness: which induced subgraphs need to be forbidden to get a χ-bounded class of graphs? One way to forbid induced 19 structures is the following: fix a graph H, and forbid every induced subdivision of H. We denote by Forb * (H) the class of graphs that does not contain any subdivision of H as an induced subgraph. The class Forb * (H) has been proved to be χ-bounded for a number of graph H. Scott [START_REF] Scott | Induced trees in graphs of large chromatic number[END_REF] proved that for any forest F , Forb * (F ) is χbounded. In the same paper, he conjectured that Forb * (H) is χ-bounded for any graph H. Unfortunately, this conjecture has been disproved (see [START_REF] Pawlik | Triangle-free intersection graphs of line segments with large chromatic number[END_REF]). However, there is no general conjecture on which graph H, Forb * (H) is χ-bounded. This question is discussed in [START_REF] Chalopin | Restricted frame graphs and a conjecture of Scott[END_REF]. We focus on the question when H = K 4 . In this case, Forb * (K 4 ) is the class of ISK4-free graphs. Since K 4 is forbidden, proving that the class of ISK4-free graphs is χ-bounded is equivalent to proving that there exists a constant c such that for every ISK4-free graph G, χ(G) ≤ c. Remark that the existence of such constant was pointed out in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF] as a consequence of a result in [START_REF] Kühn | Induced subdivisions in K s,s -free graphs of large average degree[END_REF], but it is rather large (≥ 2 2 2 25 ) and very far from these two conjectures:

Conjecture 2.1.1 (Lévêque, Maffray, Trotignon 2012 [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]). If G is an ISK4-free graph, then χ(G) ≤ 4.

Conjecture 2.1.2 (Trotignon, Vušković 2016 [49]). If G is an {ISK4, triangle}-free graph, then χ(G) ≤ 3.

No better upper bound is known even for the chromatic number of {ISK4, triangle}-free graphs. However, attempts were made toward these two conjectures. The optimal bound is known for the chromatic number of {ISK4, wheel}-free graphs and {ISK4, triangle, C 4 }-free graphs: Theorem 2.1.3 (Lévêque, Maffray, Trotignon 2012 [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]). Every {ISK4, wheel}-free graph is 3-colorable.

Theorem 2.1.4 (Trotignon, Vušković 2016 [49]). Every ISK4-free graph of girth at least 5 contains a vertex of degree at most 2 and is 3-colorable.

The proof of Theorems 2.1.3 and 2.1.4 relies on structural decompositions. One way to prove Conjectures 2.1.1 and 2.1.2 is to find a vertex of small degree. This approach is successfully used in [START_REF] Trotignon | On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph[END_REF] to prove Theorem 2.1.4. Two following conjectures will imply the correctness of Conjectures 2.1.1 and 2.1.2 (as shown in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]): However, we find a new bound for the chromatic number of ISK4-free graphs using another approach. Our main results are the following theorems: Theorem 2.1.7. Let G be an {ISK4, triangle}-free graph. Then χ(G) ≤ 4.

Theorem 2.1.8. Let G be an ISK4-free graph. Then χ(G) ≤ 24.

Remark that the bounds we found are much closer to the bound of the conjectures than the known ones. The main tool that we use to prove these theorems is classical. It is often used to prove χ-boundedness results relying on the layers of neighborhood. This section is organized as follows. We first introduce some notations in Section 2.1.2. Sections 2.1.3 and 2.1.4 are devoted to the proof of Theorem 2.1.7 and 2.1.8, respectively.

Preliminaries

In this section, we present some notations and useful lemmas which will be used later in our proof. Let G = (V, E) be a graph, we denote by |G| the number of its vertices. If the context is clear, we will sometimes write G for V (G). A complete bipartite or tripartite graph is thick if it contains a K 3,3 . Let S = {u 1 , u 2 , u 3 , u 4 } induces a square (i.e. C 4 ) in G with u 1 , u 2 , u 3 , u 4 in this order along the square. A link of S is a path P of G with ends p, p such that either p = p and N S (p) = S, or N S (p) = {u 1 , u 2 } and N S (p ) = {u 3 , u 4 }, or N S (p) = {u 1 , u 4 } and N S (p ) = {u 2 , u 3 }, and no interior vertex of P has a neighbor in S. A rich square is a graph K that contains a square S as an induced subgraph such that K \ S has at least two components and every component of K \ S is a link of S. For example, K 2,2,2 is a rich square (it is the smallest one). We refer the reader to Chapter 1 for the remaining notions (clique cutset, proper 2-cutset, prism, . . . ).

We use in this section some decomposition theorems from [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]:

Lemma 2.1.9 (see Lemma 3.3 in [38]). Let G be an ISK4-free graph that contains K 3,3 . Then either G is a thick complete bipartite or complete tripartite graph, or G has a clique cutset of size at most 3.

Lemma 2.1.10 (see Lemmas 6.1 and 7.2 in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]). Let G be an ISK4-free graph that contains a rich square or a prism. Then either G is the line graph of a graph with maximum degree 3, or G is a rich square, or G has a clique cutset of size at most 3 or G has a proper 2-cutset.

Reducing a flat path P of length at least 2 means deleting its interior and adding an edge between its two ends. The following lemma shows that a graph remains ISK4-free after reducing a flat path: Lemma 2.1.11 (see Lemma 11.1 in [38]). Let G be an ISK4-free graph. Let P be a flat path of length at least 2 in G and G be the graph obtained from G by reducing P . Then G is ISK4-free.

It is shown in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF] that clique cutsets and proper 2-cutsets are useful for proving Conjecture 2.1.1 in the inductive sense. If we can find such a cutset in G, then we immediately have a bound for the chromatic number of G, since χ(G) ≤ max{χ(G 1 ), χ(G 2 )}, where G 1 and G 2 are two blocks of decomposition of G with respect to that cutset (see the proof of Theorem 1.4 in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]). Therefore, we only have to prove Conjecture 2.1.1 for the class of {ISK4, K 3,3 , prism, K 2,2,2 }-free graphs and prove Conjecture 2.1.2 for the class of {ISK4, K 3,3 , triangle}-free graphs since the existence of K 3,3 , prism or K 2,2,2 implies a good cutset or a structure that can be appropriately colored by Lemmas 2.1.9 and 2.1.10.

For S, C ⊆ V (G), we say that S dominates C if N C (S) = C. The distance between two vertices x, y in V (G) is the length of a shortest path from x to y in G. Let u ∈ V (G) and i be an integer, we denote by N i (u) the set of vertices of G that are of distance exactly i from u. Note that there are no edges between N i (u) and N j (u) for every i, j such that |i -j| ≥ 2.

Lemma 2.1.12. Let G be a graph, u ∈ V (G) and i be an integer ≥ 1. Let x, y be two distinct vertices in N i (u). Then, there exists a path P in G from x to y such that

V (P ) ⊆ {u} ∪ N 1 (u) ∪ . . . ∪ N i (u) and |V (P ) ∩ N j (u)| ≤ 2 for every j ∈ {1, . . . , i}.
Proof. We prove this by induction on i. If i = 1, we have x, y ∈ N 1 (u). If xy ∈ E(G), we choose P = xy, otherwise, choose P = xuy. Suppose that the lemma is true until i = k, we prove that it is also true for i = k +1. If xy ∈ E(G), we choose P = xy. If x and y have a common neighbor x in N k (u), then we choose P = xx y. Otherwise, let x , y be the vertices in N k (u) such that x x, y y ∈ E(G). Note that xy , x y / ∈ E(G). We choose P = P ∪ {x, y}, where P is the path with two ends x and y generated by applying induction hypothesis. Such a path P in Lemma 2.1.12 is called an upstairs path of {x, y}. For three distinct vertices x, y, z ∈ V (G), a graph H is a confluence of {x, y, z} if it is one of the two following types:

• Type 1: -V (H) = V (P x ) ∪ V (P y ) ∪ V (P z ).
-P x , P y , P z are three paths having a common end u and P x \ u, P y \ u, P z \ u are pairwise disjoint. The other ends of P x , P y , P z are x, y, z, respectively.

-These are the only edges in H.

• Type 2:

-V (H) = V (P x ) ∪ V (P y ) ∪ V (P z ).
-P x is a path with ends x and x .

-P y is a path with ends y and y .

-P z is a path with ends z and z .

-P x , P y , P z are pairwise disjoint.

x y z is a triangle.

-These are the only edges in H.

If H is a confluence of Type 1, the vertex u is called the center of H and if H is a confluence of Type 2, the triangle x y z is called the center triangle of H. Note that the length of P x can be 0 when x = u (for Type 1) or x = x (for Type 2). Lemma 2.1.13. Let G be a graph, u ∈ V (G) and i be an integer ≥ 1. Let x, y, z be three distinct vertices in N i (u). Then, there exists a set S ⊆ {u}∪N

1 (u)∪. . .∪N i-1 (u) such that G[S ∪ {x, y, z}] is a confluence of {x, y, z}. Proof. Let G be the subgraph of G induced by {u} ∪ N 1 (u) ∪ . . . ∪ N i-1 (u) ∪ {x, y, z}.
It is clear that G is connected. Let P be a path in G from x to y and Q be a path in G from z to P (one end of Q is in P ). We choose P and Q subject to minimality of

|V (P ∪ Q)|. It is easy to see that G[V (P ∪ Q)] is a confluence of {x, y, z}.
The notions of upstairs path and confluence are very useful to find induced structures in our graph since they establish a way to connect two or three vertices of the same layer through only the upper layers. Lemma 2.1.14. Let G be a graph and u ∈ V (G). Then:

χ(G) ≤ max i odd χ(G[N i (u)]) + max j even χ(G[N j (u)]).
Proof. It is clear that in G, there are no edges between N i (u) and N j (u) if i = j and i, j are of the same parity. Therefore, we can color all the odd layers with max i odd χ(G[N i (u)]) colors and all the even layers with max j even χ(G[N j (u)]) other colors. The lemma follows.

Proof of Theorem 2.1.7

The next lemma shows that if there is a set S that dominates some hole C, then there must exist some vertices in S which have very few (one or two) neighbors in C.

Lemma 2.1.15. Let G be an {ISK4, triangle, K 3,3 }-free graph and C be a hole in G. Let S ⊆ V (G) \ C such that S dominates C. Then one of the following cases holds:

1. There exist four distinct vertices u 1 , u 2 , u 3 , u 4 in S and four distinct vertices

v 1 , v 2 , v 3 , v 4 in C such that for i ∈ {1, 2, 3, 4}, N C (u i ) = {v i }.
2. There exist three distinct vertices u 1 , u 2 , u 3 in S and three distinct vertices

v 1 , v 2 , v 3 in C such that for i ∈ {1, 2, 3}, N C (u i ) = {v i } and v 1 , v 2 , v 3 are pairwise non-adjacent.
3. There exist three distinct vertices u 1 , u 2 , u 3 in S and four distinct vertices

v 1 , v 2 , v 3 , v 3 in C such that N C (u 1 ) = {v 1 }, N C (u 2 ) = {v 2 }, N C (u 3 ) = {v 3 , v 3 } and v 1 , v 3 , v 2 , v 3 appear in this order along C.
Proof. We prove Lemma 2.1.15 by induction on the length of hole C. First, suppose that the length of C is 4 and

C = c 0 c 1 c 2 c 3 c 0 .
Since G is triangle-free, a vertex in S can only have one or two neighbors in C. We consider two cases:

• If some vertex u ∈ S has two neighbors in C, w.l.o.g, suppose N C (u) = {c 0 , c 2 }.
Since S dominates C, there exists some vertices v, w ∈ S such that vc 1 , wc

3 ∈ E. If v = w then {u, v} ∪ C induces K 3,3 (if uv ∈ E) or an ISK4 (if uv / ∈ E)
, a contradiction. Therefore, v = w and u, v, w are three vertices satisfying output 3 of the lemma.

• If every vertex in S has exactly one neighbor in C, output 1 of the lemma holds.

Now, we may assume that |C| ≥ 5 and the lemma is true for every hole of length at most |C| -

1. A vertex u ∈ S is a bivertex if N C (u) = {u , u } and the two paths P 1 , P 2 from u to u in C are of lengths at least 3. Suppose that S contains such a bivertex u. Let C 1 = P 1 ∪ {u}, C 2 = P 2 ∪ {u}, note that |C 1 |, |C 2 | < |C|. Consider the graph G obtained from G as follows: V (G ) = V (G) ∪ {a, b, c}, E(G ) = E(G) ∪ {au, bu , cu }. It is clear that G is {ISK4, triangle, K 3,3 }-free. Let S 1 = {v ∈ S \ u|N C 1 (v) = ∅} ∪ {a, b, c} and S 2 = {v ∈ S \ u|N C 2 (v) = ∅} ∪ {a, b, c}.
By applying the induction hypothesis on S 1 and C 1 , we obtain that there is some vertex x ∈ S such that x has exactly one neighbor in P 1 and this neighbor is in P * 1 (x can be adjacent to u). We claim that x has exactly one neighbor in C. Indeed, if

x has exactly one neighbor

x in P * 2 then C ∪ {x, u} induces an ISK4 (if xu / ∈ E(G)) or C 1 ∪ {x} ∪ Q induces an ISK4 (if xu ∈ E(G))
, where Q is the shorter path in one of the two paths in C: x P 2 u and x P 2 u , a contradiction. If x has at least two neighbors in P * 2 , let x , x be the neighbors of x closest to u , u on P * 2 , respectively.

Then C 1 ∪ {x} ∪ x P 2 u ∪ x P 2 u induces an ISK4 (if xu / ∈ E(G)) or C 1 ∪ {x} ∪ x P 2 u induces an ISK4 (if xu ∈ E(G)), a contradiction. So, x has no neighbor in P * 2
and has exactly one neighbor in C as claimed. Similarly, by applying the induction hypothesis on S 2 and C 2 , we know that there is some vertex y ∈ S such that y has exactly one neighbor in P * 2 and this is also its only neighbor in C. Now, {x, y, u} satisfies output 3 of the lemma. Hence, we may assume that S contains no bivertex.

Note that since G is ISK4-free, no vertex in S has exactly three neighbors in C. Suppose that there is some vertex u in S which has at least four neighbors in C. Let N C (u) = {u 0 , . . . , u k } where u 0 , . . . , u k (k ≥ 3) appear in that order along C. Let P u (i, i + 3) be the path of C from u i to u i+3 which contains u i+1 and u i+2 and define amp(u, C) = max k i=0 |P u (i, i + 3)| (the index is taken modulo k + 1). Note that this notion is defined only for a vertex with at least four neighbors in

C. Let v ∈ S be such that amp(v, C) is maximum. Similarly, let N C (v) = {v 0 , . . . , v k } where v 0 , . . . , v k (k ≥ 3) appear in that order along C. W.l.o.g suppose that P v (0, 3)
is the longest path among all paths of the form P v (i, i + 3). Let P 0 , P 1 , P 2 be the subpaths of

P v (0, 3) from v 0 to v 1 , v 1 to v 2 , v 2 to v 3 , respectively. Let C 0 = {v} ∪ P 0 , C 1 = {v} ∪ P 1 and C 2 = {v} ∪ P 2 . Consider the graph G obtained from G as follows: V (G ) = V (G) ∪ {a, b, c}, E(G ) = E(G) ∪ {av, bv 0 , cv 1 }. It is clear that G is {ISK4, triangle, K 3,3 }-free. Let S 0 = {u ∈ S \ v|N C 0 (u) = ∅} ∪ {a, b, c}.
By applying the induction hypothesis on S 0 and C 0 , we obtain that there is some vertex x ∈ S such that x has exactly one neighbor x 0 in P 0 and x 0 is in P * 0 (x can be adjacent to v). We claim that x has exactly one neighbor in C. Suppose that x has some neighbor in P 1 . Let x 1 , x 2 be the neighbors of x in P 1 which are closest to v 1 and v 2 , respectively (x 1 and x 2 could be equal). Then we have {x, v}

∪ P 0 ∪ v 1 P 1 x 1 ∪ v 2 P 1 x 2 induces an ISK4 (if xv / ∈ E(G)) or {x, v} ∪ P 0 ∪ v 1 P 1 x 1 induces an ISK4 (if xv ∈ E(G)
), a contradiction. Therefore, x has no neighbor in P 1 . Suppose that x has some neighbor in P 2 , let x 1 be the neighbor of

x in P 2 which is closest to v 2 . Let Q be the path from x 0 to x 1 in C which contains v 1 . We have {x, v} ∪ Q ∪ v 0 P 0 x 0 induces an ISK4 (if xv / ∈ E(G)) or {x, v} ∪ Q induces an ISK4 (if xv ∈ E(G)
), a contradiction. Hence, x has no neighbor in P 2 . Now if x has at least four neighbors in C, amp(x, C) > amp(v, C), a contradiction to the choice of v. Hence, x can have at most one neighbor in the path from v 0 to v 3 in C which does not contain v 1 . Suppose x has one neighbor x in that path. By the assumption that we have no bivertex,

x v 0 , v 0 x 0 ∈ E(G). Let Q be the path from v k to x in C which does not contain v 0 . We have {x, x , v 0 , x 0 , v} ∪ Q ∪ v 1 P 0 x 0 induces an ISK4 (if xv / ∈ E(G)) or {x, x , v 0 , x 0 , v} ∪ Q induces an ISK4 (if xv ∈ E(G)
), a contradiction. Hence, x 0 is the only neighbor of x in C, as claimed. Similarly, we can prove that there exist two vertices y, z ∈ S such that they have exactly one neighbor in C which are in P * 1 , P * 2 , respectively. Note that the proof for y is not formally symmetric to the one for x and z, but the proof is actually the same. In particular, a vertex y with a unique neighbor in P * 1 , no neighbor in P 0 , P 2 and at least four neighbors in C also yields a contradiction to the maximality of amp(v, C). Therefore, {x, y, z} satisfies output 2 of the lemma. Now, we can assume that no vertex in S has at least four neighbors in C.

Hence, every vertex in S either has exactly one neighbor in C or exactly two neighbors in C and is not a bivertex. Suppose there is some vertex u that has two neighbors u , u on C and let x ∈ C be such that xu , xu ∈ E. Let v ∈ S be a vertex adjacent to x. If v has another neighbor x in C then x must be adjacent to u or u , since v is not a bivertex. So, we have that {u, v, x , u , x, u } induces an ISK4 (if

uv ∈ E(G)) or {u, v} ∪ C induces an ISK4 (if uv / ∈ E(G)
), a contradiction. So, v has only one neighbor x in C. By the same argument, some vertex in V (C) \ {u , x, u } is the unique neighbor in C of some vertex in S. Hence, if we have at least one vertex which has two neighbors on C, then output 3 holds. If every vertex has exactly one neighbor in C, the output 1 holds, which completes the proof.

Lemma 2.1.16. Let G be an {ISK4, triangle, K 3,3 }-free graph and u ∈ V (G). For every i ≥ 1, G[N i (u)] does not contain any hole. Proof. Suppose for some i, G[N i (u)] contains a hole C. For every vertex v ∈ C, there exists a vertex v ∈ N i-1 (u) such that vv ∈ E. Hence there exists a subset S ⊆ N i-1 (u) such that S dominates C. Let us apply Lemma 2.1.15 for S and C:

• If output 1 or 2 of Lemma 2.1.15 holds, then there exist three distinct vertices

u 1 , u 2 , u 3 in S and three distinct vertices v 1 , v 2 , v 3 in C such that for i ∈ {1, 2, 3}, N C (u i ) = {v i }. By Lemma 2.1.13, since G is triangle-free, there exists a confluence F of {u 1 , u 2 , u 3 } of Type 1, so F ∪ C induces an ISK4, a contradiction.
• If output 3 of Lemma 2.1.15 holds, then there exist two distinct vertices u 1 , u 2 in S and three distinct vertices

v 1 , v 2 , v 2 in C such that N C (u 1 ) = v 1 , N C (u 2 ) = {v 2 , v 2 }
. By Lemma 2.1.12, there exists an upstairs path P of {u 1 , u 2 }, so P ∪ C induces an ISK4, a contradiction.

Proof of Theorem 2.1.7 We prove the theorem by induction on the number of vertices of G. Suppose that G has a clique cutset K. So G \ K can be partitioned into two sets X, Y such that there is no edge between them. By induction hypothesis

χ(G[X ∪K]) ≤ 4 and χ(G[Y ∪K]) ≤ 4, therefore χ(G) = max{χ(G[X ∪K]), χ(G[Y ∪ K])} ≤ 4.
Hence we may assume that G has no clique cutset. If G contains a K 3,3 , then by Lemma 2.1.9, G is a thick complete bipartite graph and χ(G) ≤ 2. So we may assume that G contains no K 3,3 . By Lemma 2.1.16, for every

u ∈ V (G), for every i ≥ 1, G[N i (u)] is a forest, hence χ(G[N i (u)]) ≤ 2. By Lemma 2.1.14, χ(G) ≤ 4
, which completes the proof.

Proof of Theorem 2.1.8

A boat is a graph consisting of a hole C and a vertex v that has exactly four consecutive neighbors in

C (N C (v) induces a C 4 if |C| = 4 or a P 4 if |C| ≥ 5).
A 4-wheel is a particular boat whose hole is of length 4. Let C 1 be the class of {ISK4, K 3,3 , prism, boat}-free graphs, C 2 be the class of {ISK4, K 3,3 , prism, 4-wheel}-free graphs and C 3 be the class of {ISK4,

K 3,3 , prism, K 2,2,2 }-free graphs. Remark that C 1 C 2 C 3 ISK4-free graphs.
Lemma 2.1.17. Let G be a graph in C 1 . Then χ(G) ≤ 6.

Proof. We prove first the following. Suppose N i (u) contains a C 4 , namely abcd. Every vertex can only have zero, one or two neighbors in abcd since a 4-wheel is a boat. Suppose there is some vertex x ∈ N i-1 (u) which has exactly two non-adjacent neighbors in {a, b, c, d}, say N abcd (x) = {a, c}. Let y be some vertex in N i-1 (u) adjacent to d and P be an upstairs path of {x, y}. If yb ∈ E, then {x, y, a, b, c, d} induces an ISK4 (if xy / ∈ E) or a K 3,3 (if xy ∈ E), a contradiction. If ya ∈ E, P ∪ {a, c, d} induces an ISK4, a contradiction. Then yc / ∈ E also by symmetry, and N abcd (y) = {d}. In this case P ∪ {a, b, c, d} induces an ISK4, a contradiction. Therefore, no vertex in N i-1 (u) has two non-adjacent neighbors in {a, b, c, d}. Now, suppose that there is some vertex x ∈ N i-1 (u) which has exactly two consecutive neighbors {a, b} in abcd. Let y be some vertex in N i-1 (u) adjacent to d and P be an upstairs path of {x, y}. If y is adjacent to c, then P ∪{a, b, c, d} induces a prism, a contradiction. If N abcd (y) = {d}, then P ∪ {a, b, c, d} induces an ISK4, a contradiction. Hence N abcd (y) = {a, d}. Let z be some vertex in N i-1 (u) adjacent to c, P xz be an upstairs path of {x, z} and P yz be an upstairs path of {y, z}. If zb ∈ E, P yz ∪ {a, b, c, d} induces a prism, a contradiction. If zd ∈ E, P xz ∪ {a, b, c, d} induces a prism, a contradiction. Hence N abcd (z) = {c}. In this case, P xz ∪ {a, b, c, d} induces an ISK4, a contradiction. Therefore, there is no vertex in N i-1 (u) having two neighbors in {a, b, c, d}. So, there are three vertices x, y, z Proof. We first prove that: for any u ∈ V (G) and i ≥ 1, G[N i (u)] contains no boat. We may assume that i ≥ 2, since G[N 1 (u)] is triangle-free, the conclusion holds for i = 1. Suppose for contradiction that G[N i (u)] contains a boat consisting of a hole C and a vertex x that has four neighbors a, b, c, d in this order on C. Since G contains no 4-wheel, we can assume that |C| ≥ 5 and {a, b, c, d} induces a P 4 . Let P be the path from a to d in C which does not go through b. Proof. We prove only N C (y) = {b}, the other conclusion is proved similarly. First, ya / ∈ E, otherwise {y, x, a, b} induces a K 4 . We also have yd / ∈ E, otherwise {x, y, b, c, d} induces a 4-wheel. If y has some neighbor in P * , let t be the one closest to a. In this case, tP a ∪ {x, y, b} induces an ISK4, a contradiction. Hence N C (y) = {b}.

∈ N i-1 (u) such that N abcd (x) = {a}, N abcd (y) = {b}, N abcd (z) = {c}. By Lemma 2.
Let t be a vertex in N i-1 (u) such that ta ∈ E and P yt be an upstairs path of {y, t}. By Claim 2.1.22, tb, tc / ∈ E. We have tx ∈ E, otherwise P yt ∪ {x, a, b} induces an ISK4. Suppose that N C (t) = {a}. There exists a confluence S of {t, y, z} by Lemma 2.1.13. If S is of Type 1, S ∪ C induces an ISK4, a contradiction. If S is of Type 2, S ∪ {a, b, c} induces an ISK4, a contradiction. Hence, t must have some neighbor in P \ {a}, let w be the one closest to d along P and P w be the path from a to w in C which contains b. Note that wa / ∈ E, since otherwise (V (C)\{b, c})∪{x, t} induces an ISK4. Proof. Suppose that t has no neighbor in

P yz . Because G[u ∪ N 1 (u) ∪ . . . ∪ N i-2 (u)] is
connected, there exists a path Q from t to some t such that Q\{t} ⊆ u∪N 1 (u)∪. . .∪ N i-2 (u) and t is the only vertex in Q which has some neighbor in P yz . If t has exactly one neighbor in P yz , then P w ∪ Q ∪ P yz induces an ISK4, a contradiction. If t has exactly two consecutive neighbors in P yz , then Q∪P yz ∪{a, b, c} induces an ISK4. If t has at least three neighbors in P yz or two neighbors in P yz which are not consecutive, let y , z be the one closest to y, z, respectively, then Q ∪ P w ∪ y P yz y ∪ z P yz z induces an ISK4, a contradiction. Then t must have some neighbor in P yz .

Let y , z ∈ P yz such that y y, z z ∈ E. Since t ∈ N i-1 (u), N Pyz (t) ⊆ {y, z, y , z }. If t has exactly one neighbor in P yz , then {t} ∪ P yz ∪ P w induces an ISK4, a contradiction. If t has exactly two neighbors in P yz , then {t, a, b, c} ∪ P yz induces an ISK4, a contradiction. If t has exactly three neighbors in P yz , then {t, b, c} ∪ P yz induces an ISK4, a contradiction. Hence, t has four neighbors in P yz or N Pyz (t) = {y, z, y , z }. In particular, ty ∈ E and {x, t, y, a, b} induces a 4-wheel, a contradiction. Hence, Proof. Let u ∈ V (G) and i ≥ 1. We claim that G[N i (u)] contains no 4-wheel. Suppose that G[N i (u)] contains a 4-wheel consisting of a hole abcd and a vertex x complete to abcd. By similar argument as in the proof of Lemma 2.1.17 (the proof of C 4 -free), the hole abcd cannot be dominated by only the vertices in N i-1 (u) which has one or two neighbors in abcd. Hence, there exists some vertex y

G[N i (u)] is boat-free. Now, for every i ≥ 1, G[N i (u)] ∈ C 1 .
∈ N i-1 (u) complete to abcd. It is clear that xy / ∈ E, otherwise {x, y, a, b} induces a K 4 . Now, {x, y, a, b, c, d} induces a K 2,2,2 , a contradiction. So, G[N i (u)] contains no 4-wheel. By Lemma 2.1.19, χ(G[N i (u)]) ≤ 12
. By Lemma 2.1.14, we have χ(G) ≤ 24, which proves the lemma.

Before the main proof, we have several lemmas proving the bound of chromatic number of some basic graphs. Proof. To prove that G is 4-colorable, we only need to prove that H is 4-edgecolorable. But since the maximum degree of H is three, this is a direct consequence of Vizing's theorem (see [6]). Proof. By the definition of a rich square, there is S = {u 1 , u 2 , u 3 , u 4 } that induces a square in G such that every component of G \ S is a link of S. Assume that u 1 , u 2 , u 3 , u 4 appear in this order along the square. We show a 4-coloring of G as follows. Assign color 1 to {u 1 , u 3 } and color 2 to {u 2 , u 4 }. Let P be a component of G \ S with ends p, p . If p = p , give it color 3. If p = p , give p, p color 3, 4, respectively and assign color 1 and 2 alternately to the internal vertices of P .

Proof of Theorem 2.1.8 We prove the theorem by induction on the number of vertices of G. Suppose that G has a clique cutset K. So G \ K can be partitioned into two sets X, Y such that there are no edges between them. By the induction hypothesis,

χ(G[X∪K]) ≤ 24 and χ(G[Y ∪K]) ≤ 24, therefore χ(G) = max{χ(G[X∪ K]), χ(G[Y ∪ K])} ≤ 24.
Hence we may assume that G has no clique cutset. If G contains a K 3,3 , then by Lemma 2.1.9, G is a thick complete bipartite graph or complete tripartite graph and χ(G) ≤ 3. So we may assume that G contains no K 3,3 .

Suppose that G has a proper 2-cutset {a, b}. So G \ {a, b} can be partitioned into two sets X, Y such that there is no edge between them. Since G has no clique cutset, it is 2-connected, so there exists a path P Y with ends a and b and with interior in Y . Let G X be the subgraph of G induced by X ∪ P Y . Note that P Y is a flat path in G X . Let G X be obtained from G X by reducing P Y . Define a graph G Y similarly. Since G X is an induced subgraph of G, it contains no ISK4. So, by Lemma 2.1.11, G X contains no ISK4. The same holds for G Y . By induction hypothesis, G X and G Y admit a 24-coloring. Since a and b have different colors in both coloring, we can combine them so that they coincide on {a, b} and obtain a 24-coloring of G. Now, we may assume that G has no proper 2-cutset. If G contains a K 2,2,2 (rich square) or a prism, then by Lemma 2.1.10, G is the line graph of a graph with maximum degree 3, or a rich square, and by Lemmas 2.1.25 and 2.1.26, χ(G) ≤ 4 < 24. Therefore, we may assume that G contains neither prism nor K 2,2,2 . So G ∈ C 3 and χ(G) ≤ 24 by Lemma 2.1.24.

Conclusion

The bound found in Theorem 2.1.7 is not only close to the one stated in Conjecture 2.1.2, but the simple structure of each layer is also interesting. We believe that it is very promising to settle Conjecture 2.1.2 by this way of looking at our class. For Theorem 2.1.8, we are convinced that the bound 24 we found could be slightly improved by this method if we look at each layer more carefully and exclude more structures, but it seems hard to reach the bound mentioned in Conjecture 2.1.1.

In the course of reviewing this result, Conjecture 2.1.2 has been proved in [START_REF] Chudnovsky | Triangle-free graphs that do not contain an induced subdivision of K 4 are 3-colorable[END_REF]. Moreover, it was done by settling also Conjecture 2.1.6. However, we prefer to keep our proof for Theorem 2.1.7 because of its nice and simple structure.

Detecting an ISK4 2.2.1 Introduction

We extend the notion of ISK4 to ISKn. For n ≥ 3, an ISKn is a subdivision of a K n . A graph that does not contain any subdivision of K n as an induced subgraph is ISKn-free. A twin wheel is a graph consisting of a hole C and a vertex with exactly three consecutive neighbors in C. Note that K 4 and twin wheels are two special kinds of ISK4.

For a fixed graph H, one can check in polynomial time whether some graph G contains a subdivision of H as a subgraph, as a consequence of the results of the Graph Minors series [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF]. However, checking whether G contains a subdivision of H as an induced subgraph is much more complicated. The question of detecting an induced subdivision of H (when H is fixed) in a given graph has been studied in [START_REF] Lévêque | Detecting induced subgraphs[END_REF]. There are certain graphs H where the problem is known to be NP-hard and graphs H where there exists a polynomial-time algorithm. For example, detecting an induced subdivision of K 3 is trivial since a graph is ISK3-free iff it is a forest. On the other hand, detecting an induced subdivision of K 5 has been shown to be NP-hard [START_REF] Lévêque | Detecting induced subgraphs[END_REF]. So far, apart from the trivial cases, we only know a polynomial-time algorithm to detect an induced subdivision of two subcubic graphs, which are K 2,3 [14] (subsivision of K 2,3 is also known as theta) and net [START_REF] Chudnovsky | Detecting an induced net subdivision[END_REF]. In this section, we answer the question of detecting an ISK4, which was asked in [START_REF] Lévêque | Detecting induced subgraphs[END_REF] and [START_REF] Chudnovsky | Detecting an induced net subdivision[END_REF]. For convenience in complexity analysis, we always denote by n the number of vertices of the input graph.

Theorem 2.2.1. There is an algorithm with the following specifications:

• Input: Graph G.

• Output:

an ISK4 in G, or the conclusion that G is ISK4-free.

• Running time: O(n 9 ).

Note that we have this theorem and several lemmas which correspond to some algorithms. Therefore, it depends on the context that we may call them theorems (lemmas) or algorithms.

Preliminaries

Let x, y, z be three distinct pairwise non-adjacent vertices in G. A graph H is an (x, y, z)-radar in G if it is an induced subgraph of G and:

• V (H) = V (C) ∪ V (P x ) ∪ V (P y ) ∪ V (P z ).
• C is an induced cycle of length ≥ 3 containing three distinct vertices x , y , z .

• P x is a path from x to x , P y is a path from y to y , P z is a path from z to z .

• P x , P y , P z are vertex-disjoint and x , y , z are the only common vertices between them and C.

• These are the only edges in H.

Note that the length of each path P x , P y , P z could be 0, therefore an induced cycle in G passing through x, y, z is also considered as an (x, y, z)-radar. Note also that an (x, y, z)-radar where the cycle C is a triangle, is a confluence of {x, y, z} of Type 2. We now prove that Theorem 2.2.1 is a direct consequence of the following lemma.

Lemma 2.2.2.

There is an algorithm with the following specifications:

• Input: A graph G, four vertices u, x, y, z ∈ V (G) such that {u, x, y, z} induces a claw with center u in G.

• Output: One of the followings:

-An ISK4 in G, or -Conclude that there is no (x, y, z)-radar in G = G \ (N [u] \ {x, y, z}).

• ). If there exists a K 4 or a twin wheel in G, then output that ISK4 in G. Otherwise, move on to next step. Now we may assume that G is {K 4 , twin wheel}-free. The following claim is true thanks to Lemma 2.2.3: G contains an ISK4 iff there exists some 4-tuple (u, x, y, z) of vertices in G such that they induce a claw with center u and there is an (x, y, z)radar in G . The last step in our algorithm is the following: generate every 4-tuple (u, x, y, z) of vertices in G such that they induce a claw with center u and run Algorithm 2.2.2 for each tuple. If for some tuple (u, x, y, z), we detect an ISK4 in G then output that ISK4 and stop. If for all the tuples, we conclude that there is no (x, y, z)-radar in G then we can conclude that G contains no ISK4. Since we have O(n 4 ) such tuples, and it takes O(n 5 ) for each tuple by Algorithm 2.2.2, the running time of our algorithm is O(n 9 ). The rest of this chapter is therefore devoted to the proof of Lemma 2.2.2. In the next section, we introduce some useful structures and the main proof is presented in Section 2.2.4.

Antennas and cables

First we introduce two useful structures in our algorithm.

Let x, y, z be three distinct pairwise non-adjacent vertices in G. An (x, y, z)antenna in G is an induced subgraph H of G such that:

• V (H) = {c} ∪ V (P x ) ∪ V (P y ) ∪ V (P z ).
• c / ∈ {x, y, z} ∪ V (P x ) ∪ V (P y ) ∪ V (P z ).

• P x is a path from x to x , P y is a path from y to y , P z is a path from z to z .

• P x , P y , P z are vertex-disjoint and at least one of them has length ≥ 1.

• cx , cy , cz ∈ E(H).

• These are the only edges in H.

• For any vertex v in G \ H:

v has no neighbor in H or exactly one neighbor in H, or v has exactly two neighbors v 1 , v 2 in H such that for some t ∈ {x, y, z}, v 1 , v 2 ∈ P t ∪ {c} and their distance in H is 1 (so they are adjacent) or 2.

We also define cable given three distinct pairwise non-adjacent vertices x, y, z in G. An (x, y, z)-cable in G is an induced subgraph H of G such that:

• H is a path from x to z going through y for some permutation (x , y , z ) of {x, y, z}.

• For any vertex v in G \ H:

v has no neighbor in H or exactly one neighbor in H, or v has exactly two neighbors v 1 , v 2 in H such that for some t ∈ {x , z }, v 1 , v 2 are in the path y Ht and their distance in H is 1 or 2, or v has exactly three neighbors in H, which are y and two neighbors of y in H.

Note that the existence of an (x, y, z)-antenna or (x, y, z)-cable in G implies that there is no vertex in G adjacent to all three vertices x, y, z.

The Steiner problem is the following. Given a graph G = (V, E) with non-negative edge weights and let S ⊆ V be a subset of the vertices, called terminals. The task is to find a minimum-weight Steiner tree -a tree in G that spans S. This problem is well-known to be NP-hard in general [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. We will use the following algorithm, which is a direct consequence of Steiner problem in graphs for a fixed number of terminals: Lemma 2.2.4. There is an algorithm with the following specifications:

• Input: A graph G, a subset X ⊆ V (G) of size k (k is fixed).
• Output: A minimum subgraph of G connecting every vertex in X (minimum with respect to the number of vertices).

• Running time: O(n 3 ).

Proof. By considering X as the set of terminals and the weight of every edge is 1, the solution for Steiner problem in G with k terminals gives a tree T (a subgraph of G) connecting X with minimum number of edges. Since T is a tree, the number of its vertices differs exactly one from the number of its edges, therefore graph G induced by V (T ) is also a solution for the problem in Lemma 2.2.4. An O(n 3 ) algorithm for Steiner problem in graphs with fixed number of terminals is given in [START_REF] Dreyfus | The Steiner problem in graphs[END_REF].

We refer the reader to Section 2.1.2 for the definition of a confluence.

Lemma 2.2.5. Given a connected graph G and three vertices x, y, z ∈ V (G), a minimum subgraph H of G connecting x, y, z induces either:

1. A confluence of {x, y, z} of Type 1, or 2. A confluence of {x, y, z} of Type 2.

Proof. If there are more edges, we would find a smaller subgraph in G connecting x, y, z, a contradiction.

From now on, we always denote by G, u, x, y, z the input of Algorithm 2.2.2 and denote by G the graph G \ (N [u] \ {x, y, z}). The following algorithm shows that we can detect some nice structures in G in polynomial time.

Lemma 2.2.6. There is an algorithm with the following specifications:

• Input: G, u, x, y, z.

• Output: One of the followings:

-An ISK4 in G, or -Conclude that there is no (x, y, z)-radar in G , or -A vertex v ∈ G adjacent to all three vertices x, y, z, or

-An (x, y, z)-antenna H in G , or -An (x, y, z)-cable H in G .
• Running time: O(n 3 ).

Proof. First, we check if x, y, z are connected in G in O(n 2 ). If they are not connected, conclude that there is no (x, y, z)-radar in G . Now suppose that they are connected, we can find a minimum induced subgraph H of G connecting x, y, z by Algorithm 2.2.4. By Lemma 2.2.5, if H is a confluence of Type 2, output H ∪ {u} as an ISK4 in G. Therefore, we may assume that H is a confluence of Type 1. If H contains a vertex adjacent to both x, y, z, output that vertex and stop. Otherwise, we will prove that H must be an (x, y, z)-antenna or an (x, y, z)-cable in G , or G contains an ISK4. It is clear that now H must have the same induced structure as an antenna or a cable. We are left to prove that the attachment of a vertex v ∈ G \ H also satisfies the conditions in both cases:

• Case 1: H has the same induced structure as an (x, y, z)-antenna.

(v) = {x , y , z , c}, {u, v, c}∪P x ∪P y induces an ISK4 in G. If N H (v) = {x , y , z }, suppose that z = z (since v is not adjacent to both x, y, z), then {u, v, c, z } ∪ P x ∪ P y induces an ISK4 in G.
v has at most two neighbors in P x ∪ {c} (this holds for P y , P z also).

If v has at least four neighbors in P x ∪ {c}, let P be a shortest path from x to c in H ∪ {v}, then P ∪ P y ∪ P z induces a graph connecting x, y, z which is smaller than H, a contradiction. If v has exactly three neighbors in P x ∪ {c}, suppose that v has no neighbor in P z (since v cannot have neighbors in both P x , P y , P z ), then {u, v, c} ∪ P x ∪ P z induces an ISK4 in G.

v cannot have neighbors in both two paths among P x , P y , P z . W.l.o.g, suppose v has neighbors in both P x and P y , we might assume that v has no neighbor in P z . If v has two neighbors in one of P x ∪ {c} and P y ∪ {c}, suppose that is P x ∪ {c}, let t be the neighbor of v in P y which is closest to c. In this case, {u, v} ∪ P x ∪ P z ∪ tP y y induces an ISK4 in G. Therefore, v has exactly one neighbor in P x and one neighbor in P y and H ∪ {u, v} induces an ISK4 in G.

-If v has exactly two neighbors in P x ∪ {c}, they must be of distance 1 or 2 in H.

Otherwise, we find a graph connecting x, y, z smaller than H, a contradiction.

• Case 2: H has the same induced structure as an (x, y, z)-cable. Suppose that H is a path from x to z going through y. Let x , z be the two neighbors of y in H such that x is closer to x in H. Denote by P x , P z the paths from x to x , z to z in H, respectively. Let v ∈ G \ H. The following is true:

v has at most two neighbors in P x ∪ {y}.

If v has four neighbors in P x ∪ {y}, let P be a shortest path from x to y in H ∪ {v}, then P ∪ P z is a subgraph connecting x, y, z which is smaller than H, a contradiction. If v has exactly three neighbors in P x ∪ {y}, then {u, v, y} ∪ P x induces an ISK4 in G.

-If v has neighbors in both P x , P z , then N H (v) = {x , y, z }.

We first show that v is adjacent to y. Suppose that v is not adjacent to y.

(v) = {x , y, z }.
-If v has exactly two neighbors in P x , they must be of distance 1 or 2 in H.

Otherwise, we find a graph connecting x, y, z smaller than H, a contradiction.

Actually, there is an alternative way to implement Algorithm 2.2.6 more efficiently by not using Algorithm 2.2.4. Basically, we only have to consider a shortest path P xy from x to y, then find a shortest path from z to P xy . By that we would obtain immediately an (x, y, z)-antenna or (x, y, z)-cable. However, we use Algorithm 2.2.4 since it gives us a more convenient proof. The first case we need to handle in Algorithm 2.2.6 is when there is some vertex v adjacent to both x, y and z. Lemma 2.2.7. There is an algorithm with the following specifications:

• Input: G, u, x, y, z, some vertex v ∈ G adjacent to x, y, z.

• Output: One of the followings:

-An ISK4 in G, or -Conclude that v is not contained in any (x, y, z)-radar in G .

• Running time: O(n 2 ).

Proof. It is not hard to see the following: v is contained in some (x, y, z)-radar in G iff there exists a path from y to z in

G x = G \ ((N [x] ∪ N [v]
) \ {y, z}) (up to a relabeling of x, y, z). Therefore, we only have to test if y and z are connected in G x (and symmetries). If we find some path P from y to z in G x , output {u, x, v} ∪ P as an ISK4. If no such path exists, we can conclude that v is not contained in any (x, y, z)-radar in G . Since we only have to test the connection three times (between y and z in G x , and symmetries), the running time of this algorithm is O(n 2 ).

We also have the following algorithm to handle with antenna. Lemma 2.2.8. There is an algorithm with the following specifications:

• Input: G, u, x, y, z, an (x, y, z)-antenna H in G .

• Output: One of the followings:

-An ISK4 in G, or -Conclude that there is no (x, y, z)-radar in G , or -Some vertex c ∈ G which is not contained in any (x, y, z)-radar in G .

• Running time: O(n 4 ).

Proof. Denote by c, x , y , z , P x , P y , P z the elements of H as in the definition of an antenna. In this proof, we always denote by N (X) the neighbor of X in G . First, we prove that any path connecting any pair of {x, y, z} in G \ c which contains at most two neighbors of c certifies the existence of an ISK4 in G. Such a path can be found by generating every pair (v, t) of neighbors of c in G , and for each pair, find a shortest path between each pair of {x, y, z} in G \ (N [c] \ {v, t}). It is clear that if such a path is found by this algorithm, then it has at most two neighbors of c and if no path is reported, we can conclude that it does not exist. Since we have O(n 2 ) pairs (v, t) and finding a shortest path between some pair of vertices in a graph takes O(n 2 ), this algorithm runs in O(n 4 ). Now we prove that such a path certifies the existence of an ISK4. Let P be a path between some pair in {x, y, z} that contains at most two neighbors of c, w.l.o.g assume that P is from x to y. We say that a path Q is a (P x , P y )-connection if one end of Q is in N (P x ), the other end is in N (P y ) and Q * ∩ (N (P x ) ∪ N (P y )) = ∅ (we make symmetric definitions for (x, z) and (y, z)). We also say that a path Q is S-independent for some S ⊆ V (G ) if Q ∩ N [S] = ∅. We consider following cases:

1. P contains no neighbor of c.

It is clear that there exists a subpath P of P such that P is a (P x , P y )connection. Furthermore, we may assume that P is P z -independent since otherwise there exists some subpath P of P which is a (P x , P z )-connection and is P y -independent. Let x , y be two ends of P which are in N (P x ) and N (P y ), respectively. In this case x and y are not adjacent to c since P contains no neighbor of c. We have the following cases based on the attachment on an antenna: (a) x and y , each has exactly one neighbor in P x and P y , respectively. Then {u} ∪ P ∪ H induces an ISK4 in G.

(b) x has exactly one neighbor in P x and y has exactly two neighbors in P y (or symmetric). Then {u, c} ∪ P ∪ P x ∪ P y induces an ISK4 in G.

(c) x and y , each has exactly two neighbors in P x and P y , respectively. Let t be the neighbor of x in P x which is closer to c. Then {u, c} ∪ P ∪ tP x x ∪ P y ∪ P z induces an ISK4 in G.

P contains exactly one neighbor of c.

Similar to the argument of the previous case, there exists a path P with two ends x and y such that P is a (P x , P y )-connection and is P z -independent. We may assume that c has exactly one neighbor c in P , otherwise we are back to previous case. In this case, at most one vertex in {x , y } can be adjacent to c (in other words, at most one vertex in {x , y } can be identical to c ). We consider the following cases:

(a) Each of {x , y } has exactly one neighbor in P x ∪{c}, and therefore exactly one neighbor in P x . Then {u, c} ∪ P ∪ P x ∪ P y induces an ISK4 in G.

(b) x has exactly one neighbor in P x ∪ {c} (this neighbor must be in P x ) and y has exactly two neighbors in P x ∪ {c} (or symmetric). If y is adjacent to c, then {u, c} ∪ P ∪ P x ∪ P y induces an ISK4 in G. Otherwise y has two neighbors in P y and {u, c} ∪ c P y ∪ P x ∪ P y induces an ISK4 in G.

(c) Each of {x , y } has exactly two neighbors in P x ∪ {c}. Since at most one of them is adjacent to c, we might assume that y is not adjacent to c. Then {u, c} ∪ c P y ∪ P y ∪ P z induces an ISK4 in G.

P contains exactly two neighbors of c.

We may assume that P is P z -independent since otherwise we have some subpath of P which is a (P z , P x )-connection or (P z , P y )-connection and contains at most one neighbor of c that we can argue like previous cases. Therefore, {u, c}∪P ∪P z induces an ISK4.

It is easy to see that above argument can be turned into an algorithm to output an ISK4 in each case. Now we can describe our algorithm for Lemma 2.2.8. First, test if there exists a path in G \ c between some pair of {x, y, z} which contains at most two neighbors of c:

1. If such a path exists, output the corresponding ISK4 in G.

If no such path exists, test the connection between each pair of {x, y, z} in

G \ c:

(a) If {c} is a cutset in G disconnecting some pair of {x, y, z}, then conclude that there is no (x, y, z)-radar in G .

(b) Otherwise, conclude that c is the vertex not contained in any (x, y, z)radar in G .

Now we explain why this algorithm is correct. If Case 1 happens, it outputs correctly an ISK4 by the argument above. If Case 2 happens, we know that there are only two possible cases for the connection between each pair of {x, y, z} in G \ c, for example for (x, y):

• x and y are not connected in G \ c, or

• Every path from x to y in G \ c contains at least three neighbors of c.

Therefore, Case 2a corresponds to one of the following cases, both lead to the conclusion that there is no (x, y, z)-radar in G :

• Each pair of {x, y, z} is not connected in G \ c.

• x is not connected to {y, z}, while y and z are still connected in G \ c (or symmetric). In this case every path from y to z in G \ c contains at least three neighbors of c.

If Case 2b happens, we know that each pair of {x, y, z} is still connected in G \ c and furthermore every path between them contains at least three neighbors of c. This implies that c is not contained in any (x, y, z)-radar, since if c is in some (x, y, z)radar, we can easily find a path between some pair of {x, y, z} in that radar containing at most two neighbors of c, a contradiction. The complexity of the whole algorithm is still O(n 4 ) since we can find an ISK4 in Case 1 in O(n 2 ) and test the connection in Case 2 in O(n 2 ).

The next algorithm deals with cable. Lemma 2.2.9. There is an algorithm with the following specifications:

• Input: G, u, x, y, z, an (x, y, z)-cable H in G .

• Output: One of the followings:

-An ISK4 in G, or -Conclude that there is no (x, y, z)-radar in G , or -Some vertex c ∈ G which is not contained in any (x, y, z)-radar in G .

• Running time: O(n 4 ).

Proof. W.l.o.g we can assume that cable H is a path from x to z containing y. Let x be the neighbor of y in H which is closer to x and z be the other neighbor of y in H. Let P x = xHx and P z = zHz . In this proof, we denote by N (X) the neighbor of X in G . We also say that a path Q is a (P x , P z )-connection if one end of Q is in N (P x ), the other end is in N (P z ) and Q * ∩ (N (P x ) ∪ N (P z )) = ∅. Before the algorithm, we first prove the followings:

(1) Every path P from x to z in G \ y containing no neighbor of y certifies an ISK4 in G.

Let P be a subpath of P such that P is a (P x , P z )-connection. Let x and z be two ends of P such that x ∈ N (P x ) and z ∈ N (P z ). Since P has no neighbor of y, both x and z are not adjacent to y. We consider the following cases based on the attachment on a cable:

(a) x and z , each has exactly one neighbor in P x and P z , respectively. Then {u} ∪ H ∪ P induces an ISK4 in G.

(b) x has exactly two neighbors in P x and z has exactly one neighbor in P z (or symmetric). Let t be the neighbor of z in P z .

• If t = z then {u, y} ∪ P ∪ P x ∪ tP z z induces an ISK4 in G.

• If t = z then {u, y, z} ∪ P ∪ P x induces an ISK4 in G.

(c) x and z , each has exactly two neighbors in P x and P z , respectively. Let t be one of the two neighbors of z which is closer to y. Then {u, y} ∪ P ∪ P x ∪ tP z z induces an ISK4 in G.

(2) Every path P from x to z in G \ y containing exactly two neighbors of y certifies an ISK4 in G.

It is clear since {u, y} ∪ P induces an ISK4 in G.

(3) Assume that every path from x to z in G \ y contains at least one neighbor of y.

If there exists some path from x to z in G \ y containing exactly one neighbor of y, then a shortest such path P satisfies that P ∪ {y} is an (x, y, z)-antenna in G , or G contains an ISK4.

It is clear that P ∪ {y} has the same induced structure as an antenna, we only have to prove the attachment on it. Let c be the only neighbor of y on P and x , z be the two neighbors of c different from y such that x is the one closer to x in P . Denote P x = xP x , P z = zP z . Let v be a vertex in G \ (P ∪ {y}), we consider the following cases:

• v is not adjacent to y. The following is true:

v cannot have neighbors on both P x and P z . If v does, there exists a path in G from x to z (passing through v) containing no neighbor of y, a contradiction.

v has at most two neighbors in P x ∪ {c}.

If v has at least three neighbors in P x ∪ {c}, they must be exactly three consecutive neighbors in P , otherwise there exists a shorter path than P satisfying the assumption. But if v has three consecutive neighbors in P x ∪ {c}, then {u, v} ∪ P induces an ISK4.

-If v has exactly two neighbors in P x ∪ {c}, they must be of distance 1 or 2 in P . Otherwise, we have a shorter path than P (passing through v) satisfying the assumption.

• v is adjacent to y. The following is true:

v cannot have neighbors on both P x and P z . If v does, N (v)∩P x = {x } and N (v)∩P z = {z }, otherwise there exists a shorter path than P (passing through v) satisfying the assumption. If v is adjacent to c, then {u, v} ∪ P induces an ISK4. If v is not adjacent to c, since v cannot adjacent to both x and z (by definition of cable), assume v is not adjacent to x (or equivalently x = x ). In this case, {u, v, y, x } ∪ P z induces an ISK4 in G.

v cannot have at least three neighbors in P x ∪ {c}.

If v does, there exists a path (passing through v) from x to z containing exactly two neighbors of y (which are v and c). This path certifies an ISK4 by (2). -v cannot have exactly two neighbors in P x ∪ {c}.

If v does, {u, v, y, c} ∪ P x induces an ISK4.

-If v has exactly one neighbor in P x ∪ {c}, it must be c.

If v has exactly one neighbor in P x ∪{c} which is not c, then {u, v, y}∪P induces an ISK4.

The above discussion shows that either G contains an ISK4 (and we can detect in O(n 2 )), or P ∪ {y} is an (x, y, z)-antenna in G . Now we describe our algorithm for Lemma 2.2.9:

1. Test if there exists a path P from x to z in G \ y containing no neighbor of y.

(a) If such a path exists, output an ISK4 by the argument in (1).

(b) If no such path exists, move to the next step.

2. Find a shortest path P from x to z in G \ y containing exactly one neighbor of y if such a path exists.

(a) If such a path P exists, by the argument in (3), either we detect an ISK4 in G, output it and stop, or we find an (x, y, z)-antenna P ∪ {y} in G , run Algorithm 2.2.8 with this antenna as input, output the corresponding conclusion.

(b) If no such path exists, move to the next step.

3. Test if there exists a path P from x to z in G \ y containing exactly two neighbors of y.

(a) If such a path P exists, output an ISK4 in G by the argument in (2).

(b) If no such path exists, conclude there is no (x, y, z)-radar in G (Since at this point, every path from x to z in G \y contains at least three neighbors of y).

Step 1 can be done in O(n 2 ) by checking the connection between x and z in G \ N [y]. Step 2 runs in O(n 3 ) by generating every neighbor t of y and for each t, find a shortest path between x and z in G \ (N [y] \ {t}). And pick the shortest one over all such paths. Since we call the Algorithm 2.2.8, step 2a takes O(n 4 ). Step 3 can be done in O(n 4 ) by generating every pair (t, w) of neighbors of y and for each pair (t, w), check the connection between x and z in G \ (N [y] \ {t, w}). Therefore, the total running time of Algorithm 2.2.9 is O(n 4 ).

Proof of Lemma 2.2.2

Now we sum up everything in previous section and describe the algorithm for Lemma 2.2.2:

1. Run Algorithm 2.2.6. Output is one of the followings: (a) An ISK4 in G: output it and stop.

(b) Conclude that there is no (x, y, z)-radar in G and stop.

(c) A vertex v adjacent to x, y, z: run Algorithm 2.2.7 with v as input.

Output is one of the followings:

i. An ISK4 in G: output it and stop. ii. Conclude that v is not contained in any (x, y, z)-radar in G : Run Algorithm 2.2.2 recursively for (G \ v, u, x, y, z).

(d) An (x, y, z)-antenna H in G : run Algorithm 2.2.8 with H as input. Output is one of the followings:

i. An ISK4 in G: output it and stop. ii. Conclude that there is no (x, y, z)-radar in G and stop. iii. Some vertex c ∈ G which is not contained in any (x, y, z)-radar in G : Run Algorithm 2.2.2 recursively for (G \ c, u, x, y, z).

(e) An (x, y, z)-cable H in G : run Algorithm 2.2.9 with H as input. Output is one of the followings:

i. An ISK4 in G: output it and stop. ii. Conclude that there is no (x, y, z)-radar in G and stop. iii. Some vertex c ∈ G which is not contained in any (x, y, z)-radar in G : Run Algorithm 2.2.2 recursively for (G \ c, u, x, y, z).

The correctness of this algorithm is based on the correctness of the Algorithms 2.2.6, 2.2.7, 2.2.8 and 2.2.9. Now we analyse its complexity. Let f (n) be the complexity of this algorithm. Since we have five cases, each case takes O(n 4 ) and at most a recursive call with the complexity f (n -1). Therefore f (n) ≤ O(n 4 ) + f (n -1) and f (n) = O(n 5 ).

Conclusion

In this section, we give an O(n 9 ) algorithm to detect an induced subdivision of K 4 in a given graph. We believe that the complexity might be improved to O(n 7 ) by first decomposing the graph by clique cutset until there is no K 3,3 (using decomposition theorem in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]). Now every (ISK4, K 3,3 )-free graph has a linear number of edges since it is c-degenerate by some constant c as shown in [START_REF] Lévêque | On graphs with no induced subdivision of K 4[END_REF]. Therefore, testing the connection in this graph takes only O(n), instead of O(n 2 ) as in the algorithm. Also, we only have to consider O(n 3 ) triples of three independent vertices and test every possible center of that claw at the same time instead of generating all O(n 4 ) claws. But we prefer to keep our algorithm as O(n 9 ) since it is simple and does not rely on decomposition theorem. We leave the following open question as the conclusion: Open question. Given a graph H of maximum degree 3, can we detect an induced subdivision of H in polynomial time?

Chapter 3

Even-hole-free graphs

A graph is even-hole-free if it does not contain any hole of even length as an induced subgraph. The study of even-hole-free graphs was motivated by perfect graphs, since these two classes have a very close relation. In fact, the decomposition technique which was developed during the study of even-hole-free graphs led to the proof of Strong Perfect Graph Conjecture 1.2.1. In this chapter, we study even-hole-free graphs with no star cutset. We give the optimal upper bound for its chromatic number in terms of clique number in Section 3.3 and a polynomial-time algorithm to color any graph in this class in Section 3.4. The latter is, in fact, a direct consequence of our proof that this class has bounded rank-width. The results of this chapter are covered in the following paper:

[III] N.K. Le. Coloring even-hole-free graphs with no star cutset, arXiv preprint, submitted.

Introduction

The structure of even-hole-free graphs was first studied by Conforti, Cornuéjols, Kapoor and Vušković in [START_REF] Conforti | Even-hole-free graphs part I: Decomposition theorem[END_REF] and [START_REF] Conforti | Even-hole-free graphs part II: Recognition algorithm[END_REF]. They were focused on showing that evenhole-free graphs can be recognized in polynomial time, and their primary motivation was to develop techniques which can then be used in the study of perfect graphs. In [START_REF] Conforti | Even-hole-free graphs part I: Decomposition theorem[END_REF], they obtained a decomposition theorem for even-hole-free graphs that uses 2-joins and star, double star and triple star cutsets, and in [START_REF] Conforti | Even-hole-free graphs part II: Recognition algorithm[END_REF], they used it to obtain a polynomial time recognition algorithm for even-hole-free graphs. That decomposition technique is actually useful since the Strong Perfect Graph Conjecture was proved in [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF] by decomposing Berge graphs using skew cutsets, 2-joins and their complements. Soon after, the recognition of Berge graphs was shown to be poly-nomial by Chudnovsky, Cornuéjols, Liu, Seymour and Vušković in [START_REF] Chudnovsky | Recognizing Berge graphs[END_REF]. A better decomposition theorem for even-hole-free graphs using only 2-joins and star cutsets was given in [START_REF] Da Silva | Decomposition of even-hole-free graphs with star cutsets and 2-joins[END_REF].

Finding a maximum clique, a maximum independent set and an optimal coloring are all known to be polynomial for perfect graphs [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF][START_REF] Grötschel | Geometric algorithms and combinatorial optimization[END_REF]. However, these algorithms rely on the ellipsoid method, which is impractical. It is still an open question to find a combinatorial algorithm for these problems. On the other hand, the complexities of finding a maximum stable set and an optimal coloring are both open for evenhole-free graphs. Note that a maximum clique of an even-hole-free graphs can be found in polynomial time, since a graph without a hole of length 4 has polynomial number of maximal cliques and one can list them all in polynomial time [START_REF] Farber | On diameters and radii of bridged graphs[END_REF].

Therefore, we would like to see if the decomposition theorem can be used to design polynomial-time algorithms for all these combinatorial problems. The general answer should be impossible since there are some kinds of decomposition which do not seem to be friendly with these problems like star or skew cutsets. On the other hand, 2-joins look very promising. Indeed, in [START_REF] Trotignon | Combinatorial optimization with 2-joins[END_REF], Trotignon and Vušković already gave the polynomial algorithms to find a maximum clique and maximum independent set in the subclasses of even-hole-free and Berge graphs which are fully decomposable by only 2-joins (namely, even-hole-free graphs with no star cutset and perfect graphs with no balanced skew-partition, homogenous pair nor complement 2-join). In [START_REF] Chudnovsky | Coloring perfect graphs with no balanced skew-partitions[END_REF], they generalize the result for Berge graphs to perfect graph with no balanced skew-partitions. Note that an O(n k ) algorithm that computes a maximum weighted independent set for a class of perfect graphs closed under complementation, yields also an O(n k+2 ) algorithm that computes an optimal coloring for the same class (see for instance [START_REF] Kratochvíl | Coloring precolored perfect graphs[END_REF][START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]). Hence, all three problems (clique, independent set and coloring) are solved for perfect graph with no balanced skew-partitions. However, the coloring problem for even-hole-free graphs with no star cutset remains open despite its nice structure. In this chapter, we prove that this class has bounded rank-width, a graph parameter which will be defined in the next section. This implies that it also has bounded clique-width (a parameter which is equivalent to rank-width in the sense that one is bounded if and only if the other is also bounded). Therefore, coloring is polynomial-time solvable for even-hole-free graphs with no star cutset by combining the two results: Kobler and Rotics [START_REF] Kobler | Edge dominating set and colorings on graphs with fixed clique-width[END_REF] showed that for any constant q, coloring is polynomial-time solvable if a q-expression is given, and Oum [START_REF] Oum | Approximating rank-width and clique-width quickly[END_REF] showed that a (8 p -1)-expression for any n-vertex graph with clique-width at most p can be found in O(n 3 ). Note that our result is strong in the sense that it implies that every graph problem expressible in monadic second-order logic formula is solvable in polynomial-time for even-hole-free graphs with no star cutset (including also finding a maximum clique and a maximum independent set).

We also know that even-hole-free graphs are χ-bounded by the concept introduced by Gyárfás [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]. In [1], it is proved that χ(G) ≤ 2ω(G) -1 for every even-hole-free graph G. One might be interested in knowing whether this bound could be improved for the class that we are considering, even-hole-free graphs with no star cutset. Let rwd(G) denote the rank-width of some graph G. The main results of this chapter are the two following theorems: Theorem 3.1.1. Let G be a connected even-hole-free graph with no star cutset. Then χ(G) ≤ ω(G) + 1.

Theorem 3.1.2. Let G be a connected even-hole-free graph with no star cutset. Then rwd(G) ≤ 3.

The rest of this chapter is organized as follows. In Section 3.2, we formally define every notion and mention all the results that we use in this chapter. The proof of Theorem 3.1.1 is presented in Section 3.3 and the proof of Theorem 3.1.2 is given in Section 3.4.

Preliminaries

Our proof heavily relies on the decomposition lemmas for even-hole-free graphs with no star cutset given by Trotignon and Vušković in [START_REF] Trotignon | Combinatorial optimization with 2-joins[END_REF]. Hence, in the first part of this section, the formal definitions needed to state these lemmas will be given. We refer the reader to Section 1.3 of Chapter 1 for the definitions of several decompositions (star cutset, clique cutset, 2-join,. . . ).

Since the goal of decomposition theorems is to break our graphs into smaller pieces that we can handle inductively, we need a way to construct them. Blocks of decomposition with respect to a 2-join (which will be defined below) are built by replacing each side of the 2-join by a path and the next lemma shows that for even-hole-free graphs, there exists a unique way to choose the parity of that path.

Lemma 3.2.1 ([48]

). Let G be an even-hole-free graph and (X 1 , X 2 , A 1 , B 1 , A 2 , B 2 ) be a split of a 2-join of G. Then for i = 1, 2, all the paths with an end in A i , an end in B i and interior in C i have the same parity.

Let G be an even-hole-free graph and (X 1 , X 2 , A 1 , B 1 , A 2 , B 2 ) be a split of a 2-join of G. The blocks of decomposition of G with respect to (X 1 , X 2 ) are the two graphs G 1 , G 2 built as follows. We obtain G 1 by replacing X 2 by a marker path P 2 of length k 2 , from a vertex a 2 complete to A 1 , to a vertex b 2 complete to B 1 (the interior of P 2 has no neighbor in X 1 ). We choose k 2 = 3 if the length of all the paths with an end in A 2 , an end in B 2 and interior in C 2 is odd (they have the same parity due to Lemma 3.2.1), and k 2 = 4 otherwise. The block G 2 is obtained similarly by replacing X 1 by a marker path P 1 of length k 1 with two ends a 1 , b 1 .

We refer the reader to Section 1.4 of Chapter 1 for the definition of a pyramid. Note that in an even-hole-free graph, the lengths of all three paths of a pyramid have the same parity. Now we introduce the last basic graph in our class.

An extended nontrivial basic graph R is defined as follows:

1. V (R) = V (L) ∪ {x, y}.
2. L is the line graph of a tree T .

3.

x and y are adjacent, x, y / ∈ V (L).

4. Every maximal clique of size at least 3 in L is called an extended clique. L contains at least two extended cliques.

5. The nodes of L corresponding to the edges incident with vertices of degree one in T are called leaf nodes. Each leaf node of L is adjacent to exactly one of {x, y}, and no other node of L is adjacent to {x, y}.

6. These are the only edges in R.

Note that the definition of the extended nontrivial basic graph we give here is simplified compared to the one from the original paper [START_REF] Da Silva | Decomposition of even-hole-free graphs with star cutsets and 2-joins[END_REF] (since they prove a decomposition theorem for a more general class, namely, 4-hole-free odd-signable graphs), but it is all we need in our proof. The following property of R is easy to observe in even-hole-free graphs with no star cutset: Lemma 3.2.2. x (and y) has at most one neighbor in every extended clique. Furthermore, if x has some neighbor in an extended clique K, then N (y) ∩ K = ∅.

Proof. If x has two neighbors a, b in some extended clique K, then N (a) \ {b} = N (b)\{a}, implying that there is a star cutset S = ({a}∪N (a))\{b} in R separating b from the rest of the graph, a contradiction. Also, if x and y both have a neighbor in a same extended clique, called a and b, respectively, then {x, a, b, y} induces a 4-hole, a contradiction.

An even-hole-free graph is basic if it is one of the following graphs:

• a clique,

• a hole,

• a long pyramid, or

• an extended nontrivial basic graph. Now, we are ready to state the decomposition theorem for even-hole-free graphs given by Da Silva and Vušković.

Theorem 3.2.3 (Da Silva, Vušković [START_REF] Da Silva | Decomposition of even-hole-free graphs with star cutsets and 2-joins[END_REF]). A connected even-hole-free graph is either basic or it has a 2-join or a star cutset.

By this theorem, we already know that even-hole-free graphs with no star cutset always have a 2-join. But we might prefer something a bit stronger for our purpose. A 2-join is called extreme if one of its block of decomposition is basic. The two following lemmas (which can be found in Sections 3 and 4 in [START_REF] Trotignon | Combinatorial optimization with 2-joins[END_REF]) say that: our blocks of decomposition with respect to a 2-join remain in the class and our class is fully decomposable by extreme 2-joins. This is convenient for an inductive proof. Lemma 3.2.4 (Trotignon,Vušković [48]). Let G be a connected even-hole-free graph with no star cutset and (X 1 , X 2 ) is a 2-join of G. Let G 1 be a block of decomposition with respect to this 2-join. Then G 1 is a connected even-hole-free graph with no star cutset. Lemma 3.2.5 (Trotignon,Vušković [48]). A connected even-hole-free graph with no star cutset is either basic or it has an extreme 2-join. By Lemmas 3.2.4 and 3.2.5, we know that even-hole-free graphs with no star cutset can be fully decomposed into basic graphs using only extreme 2-joins. However, we need a little more condition to avoid confliction between these 2-joins, that is, every 2-join we use is non-crossing, meaning that every marker path in the process always lies entirely in one side of every following 2-joins (the edges between X 1 and X 2 do not belong to any marker path). Now we define the 2-join decomposition tree for this purpose. Note that this definition we give here is not only for even-hole-free graphs with no star cutset, but also works in a more general sense. It is well defined for any graph class with its own basic graphs. Let D be a class of graphs and B ⊆ D be the set of basic graphs in D. Given a graph G ∈ D, a tree T G is a 2-join decomposition tree for G if:

• Each node of T G is a pair (H, S), where H is a graph in D and S is a set of disjoint flat paths of H.

• The root of T G is (G, ∅).

• Each non-leaf node of T G is (G , S ), where G has a 2-join (X 1 , X 2 ) such that the edges between X 1 and X 2 do not belong to any flat path in S . Let S 1 , S 2 ⊆ S be the set of the flat paths of

S in G [X 1 ], G [X 2 ]
, respectively (note that S = S 1 ∪ S 2 ). Let G 1 , G 2 be two blocks of decomposition of G with respect to this 2-join with marker paths P 2 , P 1 , respectively. The node (G , S ) has two children, which are

(G 1 , S 1 ∪ {P 2 }) and (G 2 , S 2 ∪ {P 1 }). • Each leaf node of T G is (G , S ), where G ∈ B.
Note that by this definition, each set S in some node (G , S ) of T G is properly defined in top-down order (from root to leaves). A 2-join decomposition tree is called extreme if each non-leaf node of it has a child which is a leaf node. Lemma 3.2.6 (Trotignon,Vušković [48]). Every connected even-hole-free graphs with no star cutset has an extreme 2-join decomposition tree. Observation 3.2.7. Every block of decomposition with respect to a 2-join of a connected even-hole-free graph with no star cutset which is basic is either a long pyramid or an extended nontrivial basic graph.

Let us review the definition of rank-width, which was first introduced in [START_REF] Oum | Approximating clique-width and branch-width[END_REF]. For a matrix M = {m ij : i ∈ R, j ∈ C} over a field F , let rk(M ) denote its linear rank.

If X ⊆ R, Y ⊆ C, then let M [X, Y ] be the submatrix {m ij : i ∈ X, j ∈ Y } of M .
We assume that adjacency matrices of graphs are matrices over GF (2).

Let G be a graph and A, B be disjoint subsets of V (G). Let M be the adjacency matrix of G over GF (2). We define the rank of (A, B), denoted by rk

G (A, B), as rk(M [A, B]). The cut-rank of a subset A ⊆ V (G), denoted by cutrk G (A), is defined by cutrk G (A) = rk G (A, V (G) \ A).
A subcubic tree is a tree such that the degree of every vertex is either one or three. We call (T, L) a rank-decomposition of G if T is a subcubic tree and L is a bijection from V (G) to the set of leaves of T . For an edge e of T , the two connected components of T \e correspond to a partition (A e , V (G)\A e ) of V (G). The width of e of the rank-decomposition (T, L) is cutrk G (A e ). The width of (T, L) is the maximum width over all edges of T . The rank-width of G, denoted by rwd(G), is the minimum width over all rank-decompositions of G (If |V (G)| ≤ 1, we define rwd(G) = 0). Observation 3.2.8. The rank-width of a clique is at most 1 and the rank-width of a hole is at most 2.

χ-bounding function 3.3.1 Special graphs

Recall that the bound of chromatic number for even-hole-free graphs (χ(G) ≤ 2ω(G)-1) is obtained by showing that there is a vertex whose neighborhood is a union of two cliques [1]. We would like to do the same things for our class. However, since our class is not closed under vertex-deletion, instead of showing that there exists a vertex whose neighborhood is "simple", we have to show that there is an elimination order such that the neighborhood of each vertex is "simple" in the remaining graph. To achieve that goal, we introduce special graphs. In fact, this is just a way of labeling vertices for the sake of an inductive proof.

A graph G is special if it is associated with a pair (C G , F G ) such that:

• C G ⊆ V (G), F G ⊆ V (G) and C G ∩ F G = ∅.
• Every vertex in F G has degree 2.

• Every vertex in C G has at least one neighbor in F G .

Note that any graph can be seen as a special graph with

C G = F G = ∅. Suppose that G has some split (X 1 , X 2 , A 1 , B 1 , A 2 , B
2 ) of a 2-join. Due to this new notion of special graph, we want to specify the pairs (C G 1 , F G 1 ) and (C G 2 , F G 2 ) for the blocks of decomposition G 1 , G 2 of G with respect to this 2-join to ensure that the two blocks we obtained are also special. Let

C i = C G ∩ X i , F i = F G ∩ X i (i = 1, 2)
, we choose the pair (C G 1 , F G 1 ) as follows:

• If |A 1 | = 1, the only vertex in A 1 is in C G and A 2 ∩ F G = ∅, then set C a = ∅, F a = {a 2 }. Otherwise set C a = {a 2 }, F a = ∅. • If |B 1 | = 1, the only vertex in B 1 is in C G and B 2 ∩ F G = ∅, then set C b = ∅, F b = {b 2 }. Otherwise set C b = {b 2 }, F b = ∅. • Finally, set C G 1 = C 1 ∪ C a ∪ C b , F G 1 = F 1 ∪ F a ∪ F b ∪ V (P * 2 ). The pair (C G 2 , F G 2 ) for block G 2 is chosen similarly. Lemma 3.3.1.
Let G be a special connected even-hole-free graph with no star cutset associated with

(C G , F G ) and (X 1 , X 2 , A 1 , B 1 , A 2 , B 2 ) be a split of a 2-join of G. Let G 1 be a block of decomposition with respect to this 2-join. Then G 1 is a special graph associated with (C G 1 , F G 1 ).
Proof. Remark that since G is 4-hole-free, one of A 1 and A 2 must be a clique (similar for B 1 and B 2 ). Now we prove that if one of A 1 and A 2 intersects F G , then the other set is of size 1. Suppose that A 1 ∩ F G = ∅, we will prove that

|A 2 | = 1. Indeed, since f ∈ A 1 ∩ F G has degree 2, |A 2 | ≤ 2. If |A 2 | = 2 then f is the only vertex in A 1 (otherwise, A 2
must be a clique and N (f ) is a clique cutset separating f from the rest of G, a contradiction to the fact that G has no star cutset). Therefore, f has no neighbor in X 1 , so there is no path from

A 1 to B 1 in G[X 1 ]
, a contradiction to the definition of a 2-join. This proves that

|A 2 | = 1. Now, G 1 is a special graph associated with (C G 1 , F G 1 ) because: 1. Every vertex f in F G 1 has degree 2. If f ∈ F 1 \ (A 1 ∪ B 1 ), then degree of f remains the same in G and G 1 . If f ∈ F 1 ∩ (A 1 ∪ B 1 ), say f ∈ F 1 ∩ A 1 , from the above remark, |A 2 | = 1, therefore the degree of f remains the same in G and G 1 . If f ∈ F a ∪ F b then |A 1 | = 1
by the way we choose F G 1 , so f has degree 2 in G 1 . If f ∈ P * 2 , then it is an interior vertex of a flat path, therefore it has degree 2.

Every vertex c in

C G 1 has at least a neighbor in F G 1 . If c ∈ C 1 and its neighbor in F G is in X 1 , then c has a neighbor in F 1 . If c ∈ C 1 and its neighbor in F G is in A 2 ∪ B 2 , say A 2 , then its neighbor in F G 1 is a 2 . If c ∈ C a ∪ C b , then its neighbor in F G 1 is one of the two ends of P * 2 .

Elimination order

Let G be a special graph associated with (C G , F G ). A vertex v ∈ V (G) is almost simplicial if its neighborhood induces a clique or a union of a clique K and a vertex u such that u / ∈ C G (u can have neighbor in K). An elimination order v 1 ,. . . ,

v k of vertices of G \ F G is nice if for every 1 ≤ i ≤ k, v i is almost simplicial in G \ (F G ∪ {v 1 , . . . , v i-1 }).
The next lemma is the core of this section. Lemma 3.3.2. Let G be a special connected even-hole-free graph with no star cutset associated with (C G , F G ). Then G \ F G admits a nice elimination order.

By setting C G = F G = ∅, we have the following corollary of Lemma 3.3.2: Corollary 3.3.3. Let G be a connected even-hole-free graph with no star cutset. Then G admits a nice elimination order.

The vertices in the remaining graph induce a subgraph of a path, therefore G \ v admits a nice elimination order. If G is a long pyramid or an extended nontrivial basic graph, we have a nice elimination order for G by Lemma 3.3.4. Now, let us prove that Lemma 3.3.2 holds for G , where (G , S ) is a non-leaf node of T G . Since T G is extreme, G admits an extreme 2-join with the split (X 1 , X 2 , A 1 , B 1 , A 2 , B 2 ) and let G 1 , G 2 be the blocks of decomposition of G with respect to this 2-join. We may assume that G 1 is basic and G 2 satisfies Lemma 3.3.2 by induction. Note that

V (G ) = (V (G 1 ) \ V (P 2 )) ∪ (V (G 2 ) \ V (P 1 )
). Now we try to specify a nice elimination order for G by combining the orders for G 1 and G 2 . Since G 1 is basic, apply Lemma 3.3.4 for G 1 with P = P 2 , we obtain the nice elimination order O 1 for G 1 \(F G 1 ∪Q P ). Remark that all the vertices in O 1 are in V (G ) since we have not eliminated Q P . By induction hypothesis, we obtain also a nice elimination order O 2 for G 2 \ F G 2 . We create an order O 2 from O 2 for V (G ) as follows (a 1 , b 1 are two ends of the marker path P 1 ):

• If a 1 ∈ C G 2 and A 1 is a clique, O 2 is obtained from O 2 by substituting a 1 in O 2
by all the vertices in A 1 (in any order), otherwise set

O 2 = O 2 \ {a 1 }. • If b 1 ∈ C G 2 and B 1 is a clique, O 2 is obtained from itself by substituting b 1 in O 2 by all the vertices in B 1 (in any order), otherwise set O 2 = O 2 \ {b 1 }. We claim that O = O 1 ⊕ O 2 is a nice elimination order for G \ F G . Let N G (u) (N G 1 (u), N G 2 (u)
) be the set of neighbors of u in the remaining graph when it is removed with respect to order O (O 1 , O 2 , respectively).

• If u is a vertex in O 1 .
-

If u / ∈ A 1 and B 1 , then N G (u) = N G 1 (u), because u is almost simplicial in G 1 then it is also almost simplicial in G at the time it was eliminated. -If u ∈ A 1 or B 1 , w.l.o.g, suppose that u ∈ A 1 , then A 1 is not a clique, because we do not eliminate Q P in O 1 . Since one of A 1 , A 2 must be a clique to avoid 4-hole, A 2 is a clique. If a 2 ∈ F G 1 , then |A 1 | = 1 and A 1 is a clique of size 1, a contradiction. Then a 2 ∈ C G 1 . Because a 2 was not eliminated at the time we remove u in order O 1 , a 2 ∈ N G 1 (u). We can obtain N G (u) from N G 1 (u) by substituting a 2 by A 2 , therefore u remains almost simplicial in G . • If u is a vertex in O 2 . -If u ∈ X 2 \(A 2 ∪B 2 ), then N G (u) = N G 2 (u), because u is almost simplicial in G 2
then it is also almost simplicial in G at the time it was eliminated.

-If u ∈ A 2 or B 2 , w.l.o.g, suppose u ∈ A 2 . We may assume that A 1 is a clique, since otherwise it was eliminated in O 1 before u, implying

N G (u) ⊆ N G 2 (u) and u is almost simplicial in G . * Suppose a 1 ∈ C G 2 . If u is eliminated after a 1 , then N G (u) = N G 2 (u) and u is almost simplicial in G . If u is eliminated before a 1 , we can obtain N G (u) from N G 2 (u) by substituting a 1 by A 1 , therefore u remains almost simplicial. * Suppose a 1 ∈ F G 2 . Since A 1 is a clique and it contains a vertex v ∈ F G , |A 1 | ≤ 2. If |A 1 | = 2, then N G (v) is a clique cutset of size 2 (star cutset) separating v from the rest of G , a contradiction. Thus A 1 = {v} and N G (u) = N G 2 (u) (since v is the only vertex in A 1 and v / ∈ G \ F G ) and u is almost simplicial in G . -If u ∈ A 1 or B 1 , w.l.o.g, suppose u ∈ A 1 , then A 1 is a clique, since otherwise it was removed in O 1 . We can obtain N G (u) from N G 2 (a 1
) by creating a clique K, which is a subclique of A 1 (K is actually the set of vertices of A 1 going after u in O 2 ), and make it complete to N G 2 (a 2 ). Therefore, u remains almost simplicial in G .

The bound is tight

Now we show how to construct for any k ≥ 3 an even-hole-free graph G k with no star cutset such that ω(

G k ) = k and χ(G k ) = k + 1. The set of vertices of G k : V (G k ) = A ∪ B ∪ C ∪ D ∪ E ∪ F
, where A, C, E are cliques of size (k -1); B, D are independent sets of size (k -1) and F is an independent set of size (k -2). The vertices in each set are labeled by the lowercase of the name of that set plus an index, for example A = {a 1 , . . . , a k-1 }. The edges of G k as follows: Proof. It is clear that ω(G k ) = k. We will show that G k is not k-colorable. Suppose we have a k-coloring of G. Because in that coloring, every clique of size k must be colored by all k different colors, then all the vertices in B must receive the same color 1. Therefore, the clique C must be colored by (k -1) left colors, and all the vertices in D must be colored by color 1 also. Therefore, the k-clique {a k-1 , e 1 , . . . , e k-1 } is not colorable since all of them must have color different from 1, a contradiction.

• A is complete to B, C is complete to D. • b i is adjacent to c i , d i is adjacent to e i (i = 1, . . . , k -1). • a k-1 is complete to E. • d 1 is complete to F . • a i is adjacent to f i (i = 1, . . . , k -2). a 1 a 2 a 3 a 4 b 1 b 2 b 3 b 4 c 1 c 2 c 3 c 4 d 1 d 2 d 3 d 4 e 1 e 2 e 3 e 4 f 1 f 2 f 3

Rank-width 3.4.1 Bounded rank-width

Recall that the definition of rank-width and rank-decomposition are given in the last part of Section 3.2. Given a graph G and some rank-decomposition (T, L) of G, a subset X of V (G) is said to be separated in (T, L) if there exists an edge e X of T corresponding to the partition (X, V (G) \ X) of V (G). Let d be an integer, we say that graph G has property P(d) if for every set S of disjoint flat paths of length at least 3 in G, there is a rank-decomposition (T, L) of G such that the width of (T, L) is at most d and every flat path P ∈ S is separated in (T, L). The next lemma shows the relation between 2-join and rank-width. Proof. Let G be a graph in D and T G be its 2-join decomposition tree. We prove that every node (G , S ) of T G satisfies the following property P (d): there is a rankdecomposition (T, L) of G such that the width of (T, L) is at most d and every flat path P ∈ S is separated in (T, L). Note that property P (d) is weaker than property P(d) since it is not required to be true for every choice of the set of disjoint flat paths, but only for a particular set S associated with G in T G . Proving this property for each node in T G implies directly the lemma since if the root of T G has property P (d), then rwd(G) ≤ d.

It is clear that every leaf node of T G has property P (d) since every basic graph has property P(d) by the assumption. Now we only have to prove that every nonleaf node (G , S ) of T G has property P (d) assuming that its two children (G 1 , S 1 ) and (G 2 , S 2 ) already have property P (d). For i ∈ {1, 2}, let (T i , L i ) be the rankdecomposition of G i satisfying property P (d). We show how to construct the rankdecomposition (T, L) of G satisfying this property. Recall that by the definition of a 2-join decomposition tree, G 1 and G 2 are two blocks of decomposition with respect to some 2-join (X 1 , X 2 ) of G together with some marker paths P 2 ∈ S 1 , P 1 ∈ S 2 , respectively. For i ∈ {1, 2}, since (G i , S i ) satisfies property P (d), P 3-i is separated in (T i , L i ) by some edge e i = u i v i of T i . Let C i , D i be the two connected components (subtrees) of T i \ e i (the tree obtained from T i by removing the edge e i ), where the leaves of C i correspond to V (G i ) \ V (P 3-i ) and the leaves of D i correspond to V (P 3-i ). W.l.o.g, we may assume that u i is in

C i and v i is in D i . The tree T is then constructed from T 1 [V (C 1 ) ∪ {v 1 }] and T 2 [V (C 2 ) ∪ {v 2 }
] by identifying u 1 with v 2 and u 2 with v 1 . Note that T is a subcubic tree and the leaves of T now correspond to V (G). The mapping L is the union of the two mappings L 1 and L 2 restricted in X 1 and X 2 , respectively. Now the node (G , S ) satisfies property P d since:

• Every flat path P ∈ S is separated in (T, L). It is true since for i ∈ {1, 2}, every path P ∈ S i is separated in (T i , L i ).

• The width of (T, L) is at most d.

It is easy to see that the width of the identified edge e = u 1 v 1 of T is 2, since it corresponds to the partition (X 1 , X 2 ) of G . For other edge e of C i (for i = 1 or 2), it corresponds to a cut of G separating a subset Z of X i from V (G )\Z, and we have cutrk G (Z) = cutrk G i (Z) (since the rank of the corresponding matrix stays the same if we just add several copies of the columns corresponding to the two ends of the marker path P 3-i ), which implies that cutrk G (Z) ≤ d.

Thanks to Lemma 3.4.1 and the existence of a 2-join decomposition tree by Lemma 3.2.6, to prove that the rank-width of even-hole-free graphs with no star cutset is at most 3, we are left to only prove that every basic even-hole-free graph with no star cutset has property P(3). Actually, by Observation 3.2.7, we do not have to prove it for cliques and holes, since they never appear in the leaf nodes of any 2-join decomposition tree of any graph in our class. Therefore, Theorem 3.1.2 is a consequence of Observation 3.2.8 and the following lemma: Lemma 3.4.2. Every basic even-hole-free graph with no star cutset, which is neither a clique nor a hole, has property P(3).

Proof. Let G be a basic even-hole-free graph with no star cutset, which is different from a clique and a hole. Since G is basic and G is neither a clique nor a hole, G must be an extended nontrivial basic graph or a long pyramid. Since the case where G is a long pyramid can be followed easily from the case where it is an extended nontrivial basic graph. We omit the details for long pyramids here.

Let G be an extended nontrivial basic graph, V (G) = V (H) ∪ {x, y}, where H is the line graph of a tree. Let S be some set of flat paths of length at least 3 in G. Now we show how to build the rank-decomposition of G satisfying the lemma.

First, we construct the characteristic tree F H for H. We choose an arbitrary extended clique in H as a root clique. Let E be the set of flat paths obtained from H by removing all the edges of every extended clique in H. Now, we define the father-child relation between two flat paths in E. A path B is the father of some path B if they have an endpoint in the same extended clique in H and any vertex of B is a cut-vertex in H which separates B from the root clique. If B is the father of B then we also say that B is a child of B. Any path in E which has only one endpoint in an extended clique is called leaf path, otherwise it is called internal path. Now, we consider each path B in E as a vertex v B in the characteristic tree F H , and associate with each node v B a set S v B = V (B). Each leaf path corresponds to a leaf in F H and each internal path corresponds to an internal node in F H , which reserves the father-child relation (if a path B is the father of some path B then v B is the father of v B in F H ). We also add a root r for F H , and the children of r are all the vertices v B , where B is a path with an endpoint in the root clique, let S r = ∅. Now, we add two special vertices x, y to attain the characteristic tree F G for G. If x (or y) is an endpoint of some flat path P in S, then we set S v = S v ∪ {x} (S v = S v ∪ {y}, respectively), where v is the leaf in F H corresponding to the leaf path in E which contains P \{x} (P \{y}, respectively). Otherwise set

S v = S v ∪{x} (S v = S v ∪{y}),
where v is a leaf in F H corresponding to any path in E having an endpoint adjacent to x (y, respectively). Now, we show how to build the rank-decomposition of G from its characteristic tree F G . We first define a special rooted tree, called k-caterpillar (k ≥ 1) to achieve that goal. For k ≥ 1, a graph I is called k-caterpillar if:

• For k = 1, V (I) = {a 1 , l 1 }, E(I) = {a 1 l 1 } and a 1 is the root of I.
• For k ≥ 2, V (I) = {a 1 , . . . , a k-1 } ∪ {l 1 , . . . , l k }, E(I) = {a i a i+1 |1 ≤ i ≤ k -2} ∪ {a i l i |1 ≤ i ≤ k -1} ∪ {a k-1 l k } and a 1 is the root of I.
Notice that in the following discussion, for the sake of construction, the rankdecomposition (T, L) we build for our graph is not exactly the same as in the definition of a rank-decomposition mentioned in Section 3.2, since we allow vertex of degree 2 in tree T , but it does not change the definition of rank-width. A flat path in G is called mixed if it contains a flat path in S but it is not a flat path in S. We start by constructing the rank-decomposition of a non-mixed flat path in G. For a non-mixed flat path P = p 1 . . . p k , we create a k-caterpillar T P which has exactly k leaves l 1 , . . . , l k as in the definition and a bijection L P maps each vertex in P to a leaf of T P such that L P (p i ) = l i . Since a mixed path can always be presented as a union of vertex-disjoint non-mixed paths P = ∪ k i=1 P i (where one end of P i is adjacent to one end of P i+1 for 1 ≤ i ≤ k -1), let (T i , L i ) be the rank-decomposition for each non-mixed path P i constructed as above, we can build the tree T P by creating a kcaterpillar I which has exactly k leaves l 1 , . . . , l k as in the definition and identify each root of T i with the leaf l i of I for 1 ≤ i ≤ k. Also, let the mapping L P from V (P ) to the leaves of T P be the union of all the mappings L i 's for 1 ≤ i ≤ k. Now, we build the rank-decomposition (T G , L G ) of G from its characteristic tree F G by visiting each node in F G in an order where all the children of any internal node is visited before its father. For a vertex v ∈ F G , denote by C v the union of all connected components of F G \ v that does not contain r.

Let F G (v) = F G [V (C v ) ∪ {v}], X v = ∪ u∈F G (v) S u .
At each node v of F G , we build the rank-decomposition (T v , L v ) of the graph G v induced by the subset X v of V (G) by induction:

1. If v is a leaf of F G , build the rank-decomposition (T v , L v ) for the flat path corresponding to v like above argument for mixed and non-mixed paths.

2. If v is an internal node of F G different from its root and v 1 , . . . , v k are its children. Let (T, L) be the rank-decomposition of the flat path corresponding to v (built by above argument for mixed and non-mixed paths) and (T i , L i ) (i = 1 . . . k) be the rank-decomposition of G[X v i ]. We build T v by constructing a (k + 1)-caterpillar having exactly (k + 1) leaves l 1 , . . . , l k+1 as in the definition and identify the root of T with l 1 , the root of T i with l i+1 for 1 ≤ i ≤ k. Let the mapping L v from X v i to the leaves of T v be the union of the mapping L and all the mappings L i 's for 1 ≤ i ≤ k.

3. If v is the root of F G and v 1 , . . . , v k are its children. Let (T i , L i ) (i = 1 . . . k) be the rank-decompositions of G[X v i ]
. We build T v by constructing a k-caterpillar having exactly k leaves l 1 , . . . , l k as in the definition and identify the root of T i with l i for 1 ≤ i ≤ k. Let the mapping L v from V (G) to the leaves of T v be the union of all the mappings L i 's for 1 ≤ i ≤ k. The rank-decomposition (T r , L r ) corresponding to the root r of F G is the desired rank-decomposition (T, L) for G (see Figure 3.4). Now we prove that this rankdecomposition construction for the extended nontrivial basic graphs G satisfies the lemma.

Proposition 3.4.3. Let (T, L) be the above constructed rank-decomposition for G. Then, every flat path P in S is separated in (T, L).

Proof. It is trivially true, because P is a non-mixed subpath of some flat path B in E, so V (P ) is separated in the rank-decomposition of B. And each flat path B of G is also separated in the rank-decomposition of G by our construction. So V (P ) is separated in (T, L). Proof. We prove by the structure of the characteristic tree F G of G. For an internal node v of F G , let v 1 , . . . , v k be its children, in some sense, the decomposition tree T v for X v is obtained by "glueing" the decomposition tree for G[S v ] and all the decomposition trees T i for G[X v i ] for 1 ≤ i ≤ k along a cut-vertex. Therefore, we consider an edge e of T v as an edge of T as well. Our goal is to prove that the width of any edge e with respect to the rank-decomposition (T, L) of G is at most 3. For the sake of induction, at each node v of F G , we prove that the width of any edge e of T v is at most 3 with respect to the rank-decomposition (T, L) of G (we mention v here just to specify an edge in our tree T ):

1. If v is a leaf in F G .
Every edge e of T v corresponds to a partition of V (G) into two parts where one of them is a subpath of the flat path corresponding to v, so the width of e is at most 2. • e corresponds to a partition (V (P ), V (G) \ V (P )) of V (G), where P is a subpath of the flat path G[S v ]. In this case, the width of e is clearly at most 2.

• e corresponds to a partition (U, V (G) \ U ) of V (G), where U is the union of several X v i 's. Let K be the extended clique intersecting every X v i . In this case, there are only three types of neighborhood of vertices of U in G \ U :

-K \ U , -x if x / ∈ U , or N (x) \ U if x ∈ U , and
-y if y / ∈ U , or N (y) \ U if y ∈ U .
Therefore, the width of e is at most 3. 3.4.2 An even-hole-free graph with no clique cutset and unbounded rank-width

It is clear that clique cutset is a particular type of star cutset. However, the class of even-hole-free graph with no clique cutset (a super class of even-hole-free graph with no star cutset) does not have bounded rank-width. Since clique-width and rank-width are equivalent, now we show how to construct for every k ≥ 4, k even an even-hole-free graph G k with no clique cutset and cwd

(G k ) ≥ k. The set of vertices of G k : V (G k ) = ∪ k i=0 A i ,
where each A i = {a i,0 , . . . , a i,k } is a clique of size (k + 1). We also have edges between two consecutive sets A i , A i+1 (i = 0, . . . , k, the indexes are taken modulo (k + 1)). They are defined as follows: a i,j is adjacent to a i+1,l iff j + l ≤ k. Lemma 3.4.5. For every k ≥ 4, k even, G k is an even-hole-free graph with no clique cutset.

Proof. By the construction, there is no hole in G k that contains two vertices in some set A i and every hole must contain at least a vertex in each set A i . Therefore, every hole in G k has exactly one vertex from each set A i , so its length is (k + 1) (an odd number). Hence, G k is even-hole-free.

We see that every clique in G k is contained in the union of some two consecutive sets A i , A i+1 . Hence, its removal does not disconnect G k . Therefore, G k has no clique cutset. Lemma 3.4.6. For every k ≥ 4, k even, cwd(G k ) ≥ k.

Proof. The graph obtained from G k by deleting all the vertices in A 0 ∪ k i=1 {a i,0 } is isomorphic to the permutation graph H k introduced in [START_REF] Golumbic | On the clique-width of some perfect graph classes[END_REF]. And because it was already proved in that paper that cwd(H k ) ≥ k, and clique-width of G k is at least the clique-width of any of its induced subgraph then cwd(G k ) ≥ k.

Note that an example of a (diamond, even-hole)-free graph with no clique cuset and unbounded rank-width was also given in [START_REF] Vušković | On rank-width of even-hole-free graphs[END_REF] (a diamond is a graph obtained from a complete graph on four vertices by removing one edge). This graph is constructed differently from ours. It is built by specifying the edges between a long path and a large clique in such a way that there is no even hole. However, our construction and theirs both contain a large clique. We do not know whether this is the case for even-hole-free graphs in general. The following question was asked in [START_REF] Cameron | On the structure of (pan, even hole)-free graphs[END_REF]: Open question. Is the rank-width of an even-hole-free graph bounded by a function of its clique number?

Chapter 4 Connected greedy coloring

A natural way to color a graph is by using a greedy algorithm: we consider the vertices of a graph in sequence and assign for each vertex the first available color. Although this algorithm does not always give the optimal solution, it is very practical and may give some information about the structure of a graph. Many researches have been done for general orders (see [START_REF] Christen | Some perfect coloring properties of graphs[END_REF][START_REF] De Werra | Heuristics for graph colorings[END_REF][START_REF] Zaker | Results on the grundy chromatic number of graphs[END_REF]7]): the complexity of computing Grundy number (i.e. maximum k such that there exists an order producing a k-coloring), the characterization of graphs where there exists a bad ordering, the complexity of recognizing (hereditary) well-colored graphs, . . . . There are many ways to choose an order of the vertices to hopefully improve the outcome of greedy algorithms. In this chapter, we mainly focus on connected orders, an order where each vertex (except the first one) has a neighbor before it in the order. Connected orders have also been studied [START_REF] Hertz | Connected sequential colorings[END_REF]2,4,7]. We know that it is NP-hard to compute connected Grundy number (a similar parameter for connected order). Some examples of graphs that are not friendly with connected orders were also given. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G and for every connected order O of H, the greedy algorithm gives H an optimal coloring. In this chapter, we give the characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs. This also implies an algorithm for recognizing good claw-free graphs. Note that the complexity of recognizing good graphs remains open. The result of this chapter is covered in the following paper:

[IV] N.K. Le, N. Trotignon. Connected greedy colouring in claw-free graphs, arXiv preprint, submitted.

Introduction

Let G be a graph and O = [v 1 , . . . , v n ] be a linear ordering of its vertices. The greedy coloring algorithm (greedy algorithm for short) applied to (G, O) consists in taking the vertices in the order O, and giving to each vertex a color equal to the smallest positive integer not used by its neighbours already colored. This obviously produces a coloring.

For every graph, there exists an order O for the vertices such that the greedy algorithm produces an optimal coloring. To see this, consider an optimal coloring π, and consider the following ordering: first take vertices with color 1, then vertices with color 2, and so on. But this method has no practical interest to compute optimal colorings, since to find the ordering, an optimal coloring has to be known.

It is also well known that for some graphs, there exist orderings that produce colorings very far from the optimal, for instance consider two disjoint sets on n vertices, say A = {a 1 , . . . , a n } and B = {b 1 , . . . , b n }. Add all possible edges between A and B, except edges a i b i , i ∈ {1, . . . , n}. This produces a bipartite graph G. However, the greedy algorithm applied to the order [a 1 , b 1 , a 2 , b 2 , . . . , a n , b n ] produces a coloring with n colors.

One might wonder for which graphs the greedy algorithm always gives an optimal solution no matter what order is given. The operation Disjoint-Union consists in building a new graph by taking the union of two vertex-disjoint graphs. The operation Complete-Join consists in building a new graph by taking the union of two vertex-disjoint graphs G 1 and G 2 , and by adding all possible edges between V (G 1 ) and V (G 2 ). Let P k denote the path on k vertices. A cograph is a P 4 -free graph. Seinsche [START_REF] Seinsche | On a property of the class of n-colorable graphs[END_REF] proved that cographs are exactly the graphs that can be produced by starting with graphs on one vertex and by repeatedly apply the operations Disjoint-Union and Complete-Join to previously constructed graphs. The graphs such that the greedy algorithm on every order gives every induced subgraph of them an optimal coloring are fully characterized. Theorem 4.1.1 (see [START_REF] De Werra | Heuristics for graph colorings[END_REF][START_REF] Christen | Some perfect coloring properties of graphs[END_REF]). For every graph G, the following properties are equivalent.

• G is a cograph.

• For every induced subgraph H of G and every linear order O of V (H), the greedy coloring algorithms applied to (H, O) produces an optimal coloring of H.

There are many ways to order the vertices of a graph with the hope to obtain a better coloring. In this paper, we focus on connected orders. An order O = [v 1 , . . . , v n ] for a graph G is connected if for every 2 ≤ i ≤ n, there exists j < i such that v j v i ∈ E(G). A connected order exists if and only if G is connected, and is efficiently produced by search algorithms such as BFS, DFS (or more simply by the algorithm generic search). We say that a graph G is good if for every connected induced subgraph H of G and every connected order O of H, the greedy algorithm produces an optimal coloring of H. Also, a connected order O of a graph G is good if it produces an optimal coloring of G. A graph or a connected order is bad if it is not good. A graph is minimally bad if it is bad and all other connected induced subgraphs of it are good. Connected orders are better than general orders for coloring bipartite graphs. Theorem 4.1.2 (see [4]). Every bipartite graph is good.

However, unlike general orders, it is not true that for every graph, there exists a connected order that provides an optimal coloring, see [2] for example. A similar claw-free example is given in The connected greedy coloring has recently been studied. In [4], they define Γ c (G) (also known as connected Grundy number ) as the maximum number k such that there exists a connected order producing a k-coloring of G. They also proved that checking if Γ c (G) ≥ k is NP-hard if k is a part of the input. In [7], they show that this problem remains NP-hard even when k = 7. A graph G is good in our definition if for every connected induced subgraph H of G, Γ c (H) = χ(H). Note that their results imply also that checking if there exists a bad connected order for a graph is NP-hard, but do not imply NP-hardness on recognizing good graphs (since a class of good graphs is hereditary by our definition). The complexity of recognizing good graphs remains open. In [2], they gave several examples of small graphs that are not friendly with connected orders. They also proved that gem (see Figure 4.2) is the unique smallest bad graph. In [START_REF] Hertz | Connected sequential colorings[END_REF], they defined a more restricted good graph with respect to connected orders and gave the complete characterization of this class. Therefore, their class is also good by our definition.

However, the list of excluded induced subgraphs for the class of good graphs is still unknown. Equivently, no description of minimally bad graphs is known. Our goal is to prove an analogue of Theorem 4.1.1 for connected orders. If we restrict our attention to claw-free graphs, we are able to give this description. This is our main result that we now state precisely. The rest of the chapter is devoted to its proof.

The main result

Note that the definition of a prism is presented in Section 1.4 of Chapter 1. Here we add the definitions of some particular types of prism. A prism is short if one of its three paths is of length 1. A prism is parity if its three paths have the same parity and is imparity otherwise. Note that a prism contains an odd hole if and only if it is imparity. A parity prism is even (odd ) if the lengths of its three paths are even (odd). rs twin wheel 4-wheel bracelet gem fish claw • The path of a twin wheel is of length at least 2.

• A bracelet has six paths of length at least 2: two paths in the sides are of even length; the other four paths are of odd length.

The graphs in Figure 4.3 have the following specifications:

• The orientation represented for each graph has no special meaning. It is an indication of how a bad connected order can be found for it. The orientation does not fully specify this order. The arrow should be seen from a small to a big vertex with respect to this order. The chromatic number of each graph is 3 and the last vertex in every bad order receives color 4.

• The hole in F 1 is odd.

• The only path in F 2 is of length ≥ 1. The orientation of the only unoriented edge depends on the parity of this path. F 2 is a gem when the length of this path is 1.

• The only path in F 3 is of length ≥ 1.

• The hole in F 5 is even.

• All paths in F 7 , F 8 , F 9 , F 10 are of length ≥ 2.

• F 7 is an imparity prism. The lower path is of different parity from the other two paths.

• The prism in F 8 is an even prism. The upper path of the prism contains two flat paths: the first one is odd, the second is even.

• The prisms in F 9 and F 10 are odd prisms.

• The upper path of the prism in F 9 contains two odd flat paths.

• The upper and lower paths of the prism in F 10 contain four even flat paths.

• The length of the only long cycle in F 11 is odd ≥ 3. If its length is 3, then F 11 is a fish.

• The length of two flat paths in F 12 is odd ≥ 3.

Our main result is the following. When X ⊆ V (G), we use the notation O[X] to denote the order induced by O on X, and O \ X to denote the order induced by O on V (G) \ X. We write O \ v instead of O \ {v}. We denote by max(X) (resp. min(X)) the maximum (resp. minimum) element in X.

Let G be a graph and O = [v 1 , . . . , v n ] be a linear ordering of its vertices. The greedy coloring algorithm starting with color 2 applied to (G, O) consists in giving v 1 color 2, and then taking the vertices from v 2 on in the order O, and giving to Proof. To prove (1), suppose that there exists a vertex v ∈ N (s k ) \ {a k } such that v < s k and π(v) = π(a k ). Let b = s k be the second neighbor of a k . Since a k < s k , by Lemma 4.2.10, a k is the source of G, or b < a k < s k . In either case, we can see that O \ a k is a connected order for G \ a k , because s k-1 < s k (and k ≥ 2).

If a k is not the source of G, order O \ a k gives an optimal coloring π of G \ a k because G is minimally bad. Morevover, for every vertex u = a k in G, we have π (u) = π(u). For u = b this is because b < a k , for the other u < s k this is because a k brings no constraint to u and for u = s k , this is because the only constraint brought by a k is also brought by v (because π(v) = π(a k )). So, π is an optimal coloring of G, a contradiction.

If a k is the source of G, then b = v 2 because s k-1 < s k . Hence, π(b) = 2. We consider the greedy algorithm starting with color 2 applied to (G \ a k , O \ a k ). This is a connected order, and it therefore provides an optimal coloring π of G \ a k by Lemma 4.2.1. Again, for every vertex of G, u = a k , we have π (u) = π(u), because the only constraint brought by a k is given to s k , and v gives the same constraint. So, π is an optimal coloring of G, a contradiction.

Let us now prove (2). By Lemma 4.2.10, we know that for i = 1, . . . , k, π(a i ) = 1 or π(a i ) = 2. If π(a k ) = 1, then suppose that for some i < k, π(a i ) = 2. No neighbor of s i smaller than s i has color 1: for a i by assumption, and all others are in N (s k ) \ {a k }, so we know this by (1). Hence, π(s i ) = 1, contradicting (1). If π(a k ) = 2, the proof is similar. Lemma 4.2.15. Suppose that G is claw-free. Let s 1 , s 2 be two vertices in G such that s 1 < s 2 and s 1 s 2 ∈ E(G). Let a 1 , a 2 be distinct vertices of degree 2 in G, such that a 1 s 1 , a 2 s 2 ∈ E(G) and a 2 < s 2 . Suppose that N (s 1 ) \ {a 1 , s 2 } = N (s 2 ) \ {a 2 , s 1 } = K, where K is a non-empty clique. Suppose that {s 1 , s 2 } is a cutset in G and C 1 , C 2 are two connected components of G \ {s 1 , s 2 } such that a 1 , a 2 ∈ C 1 and K ⊆ C 2 .

So, π(a 1 ) = π(a 2 ) = 2, s 1 < a 1 and there exist vertices v ∈ K, p, q ∈ C 2 \ K such that vpq is a triangle, v < s 1 and v < s 2 .

Proof. We first prove that v = min(K) < s 2 . Otherwise, s 2 < v. Also, v = min(C 2 ) because O is connected. In G ≤s 2 , s 1 and s 2 both have degree at most 2, so π(s 1 ), π(s 2 ) ∈ {1, 2, 3}. In G ≤v , v has degree 2, so π(v) ∈ {1, 2, 3}. Hence, the clique cutset S = {s 1 , s 2 }, C 2 and v contradict Lemma 4.2.7. This proves our claim.

By Lemma 4.2.14, we consider two cases.

Case 1: π(a 1 ) = π(a 2 ) = 1. By Lemma 4.2.14, π(v) = 1. So, there exists x adjacent to v with x < v and π(x) = 1. Note that x / ∈ K because x < v and x / ∈ {s 1 , s 2 } because π(x) = 1. If s 1 < v, then G <v is disconnected (x and s 1 are in different components). Therefore, Otherwise, there exists v < b such that π(v) = π(b). Note in particular that by Lemma 4.2.2, b = v n . Also, the existence of v implies that O \ b is a connected order for G \ b. We then see that for every vertex y = b, π G\b,O\b (y) = π G,O (y), a contradiction to Lemma 4.2.3. This proves Claim 4.3.2. This implies that a has degree at least 2 in G ≤a , so a has an in-neighbor u in L. So, if a < a, then G <a is diconnected (a and u are in different components). Hence, a < a . So there exists a vertex in L with color 1 (to ensure that a has color at least 3). Since a < a , we know by Lemma 4. A graph H is an even birdcage in G if:

• V (H) = ∪ k i=1 V (P i ) ∪ C a ∪ C b for some k ≥ 3.
• ∀i ∈ {1, . . . , k}, P i is a flat path in G of even length ≥ 2 with two ends a i , b i (all a i 's and b i 's are distinct).

• S a = {a Let a ∈ R i . If a is not adjacent to x, then {v i , v i-1 , x, v i+1 , a} induces a gem, a contradiction. If a is adjacent to x, then {x, v i-2 , v i-1 , v i , a} induces a gem, a contradiction. So, R i = ∅. This proves Claim 4.4.6. Otherwise, if there exists some path P from a vertex in C a to some vertex in C c or C d , then G contains an even prism, contradicting Lemma 4.4.12. If there exists some path P from a vertex in C a to some vertex in C b , then P is of odd length and therefore H ∪ P is a bigger bracelet system, a contradiction to the choice of H. This proves Claim 4.4.19.

We also have similar statement for S b , S c and S d . By Claims 4.4.17 Otherwise, if there is a path from some vertex in K i to some vertex in K j for some i = j, then G contains a bracelet, a contradiction. If there is a path from some vertex in C a to some vertex in K i for some i, then G contains F 7 or an even prim, a contradiction. If there is a path P from a vertex in C a to some vertex in C b , then 4.4 can be turned into a polynomial algorithm for recognizing this class, where each structure in Section 4.3 corresponds to a kind of decomposition. A full characterization of good graphs seems hard to achieve, as we observe that the actual structure of minimally bad graphs could be much more complicated. The following question is open: Open question. Is the chromatic number of every minimally bad graph 3?

We see that this is true for claw-free graphs. The next step would be finding the characterization for good perfect graphs, or some interesting subclasses of perfect graphs.

Conclusion

Throughout the thesis, we have studied the coloring and recognition problem for several graph classes. In this last chapter, let us review all these and discuss some open questions.

In Chapter 2, we focus on ISK4-free graphs. The study of this class is motivated by Scott's question [START_REF] Scott | Induced trees in graphs of large chromatic number[END_REF] on χ-boundedness of graph classes defined by forbidding all the subdivisions of a fixed graphs and the dichotomy between polynomial and NP-hardness on detecting an induced subdivision [START_REF] Lévêque | Detecting induced subgraphs[END_REF]. We prove that the chromatic number of ISK4-free graphs is bounded by some small constant (and even smaller in triangle-free case) and propose a polynomial-time recognition algorithm. Recall that F orb * (H) is a graph class defined by forbidding all subdivision of H as induced subgraphs. There are examples of graph H such that F orb * (H) is χ-bounded and examples of graph H where F orb * (H) is not χ-bounded. Similarly, there exist some examples of graph H such that F orb * (H) can be recognized in polynomial-time and examples of graph H where F orb * (H) is NP-hard to detect. However, the complete characterization of whether F orb * (H) is χ-bounded and whether F orb * (H) is recognizable in polynomial-time is still very far from completion. We do not even know an instance of a subcubic graph H where detecting F orb * (H) is NP-hard. In other words, we do not know if it is possible to detect F orb * (H) in polynomial-time for every subcubic graph H.

In Chapter 3, we studied even-hole-free graphs with no star cutset. This was motivated by even-hole-free graphs (a graph class which is closely related to perfect graphs) and the use of decomposition technique in solving some optimization problems. We prove the optimal χ-bounding function for even-hole-free graphs with no star cutset and also show that this class has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm. The complexity of finding a maximum stable set and an optimal coloring for even-hole-free graphs remains open, even though we know the positive answers for a number of its subclasses.

In Chapter 4, connected greedy coloring is considered. This was motivated by the greedy coloring algorithm applied to some order of the vertices. Many researches 97 have been done for general orders (see [START_REF] Christen | Some perfect coloring properties of graphs[END_REF][START_REF] De Werra | Heuristics for graph colorings[END_REF][START_REF] Zaker | Results on the grundy chromatic number of graphs[END_REF]7]): the complexity of computing Grundy number, the characterization of graphs where there exists a bad ordering, the complexity of recognizing (hereditary) well-colored graphs, . . . . Connected orders have also been studied [START_REF] Hertz | Connected sequential colorings[END_REF]2,4,7]. We know that it is NP-hard to compute connected Grundy number. Some examples of graphs that are not friendly with connected orders were also given. However, we know very little about the characterization of good graphs with respect to connected orders. In this chapter, we gave the complete characterization of a good claw-free graphs in terms of minimal forbidden induced subgraphs. This implies also a polynomial-time algorithm for recognizing good clawfree graphs. We would like to know the complexity of recognizing and the full characterization of good graphs in general. The next direction should be to study this question for some interesting classes, for example perfect graphs.

  's Strong Perfect Graph Conjecture on perfect graphs remained open for more than 40 years. Until 2002, it was settled by Chudnovsky, Robertson, Seymour and Thomas. It is now known as the Strong Perfect Graph Theorem. Their proof based on a deep structural decomposition theorem.

  .1 for example). Given a graph H, the line graph of H, denoted by L(H), is the graph with vertex set E(H) and edge set {ef : e ∩ f = ∅}. The edge subdivision operation for an edge uv ∈ E(G) is the deletion of uv from G and the addition of two edges uw and wv along with the new vertex w. This operation generates a new graph H = (V ∪ {w}, (E \ {uv}) ∪ {uw, wv}). A subdivision of G is a graph that can be derived from G by a sequence of edge subdivision operations. See Figure 1.2 for an example of subdivisions and line graphs.

2 Figure 1 . 1 :Figure 1 . 2 :

 21112 Figure 1.1: An example of a complete bipartite graph and a complete tripartite graph

(a) P 6 (b) C 6 Figure 1 . 3 :

 6613 Figure 1.3: An example of paths and holes

  .4).

Figure 1 . 4 :

 14 Figure 1.4: Some small graphs

Figure 1 . 5 :

 15 Figure 1.5: Example of Truemper configurations

Claim 2 . 1 . 18 .

 2118 Let u ∈ V (G) and i ≥ 1. Then G[N i (u)] contains no triangle and no C 4 .Proof. Suppose G[N i (u)] contains a triangle abc. No vertex is complete to abc since G is K 4 -free. Suppose that there is some vertex x ∈ N i-1 (u) which has exactly two neighbors in the triangle, w.l.o.g. assume that they are a and b. Let y be some vertex in N i-1 (u) adjacent to c and P be an upstairs path of {x, y}. If y has exactly one neighbor in abc (which is c), then P ∪ {a, b, c} induces an ISK4, a contradiction. Hence y must have another neighbor in C, say a up to symmetry. In this case, P ∪ {a, b, c} induces a boat, a contradiction. Then every vertex in N i-1 (u) has exactly one neighbor in abc. Suppose there are three vertices x, y, z ∈ N i-1 (u) such that N abc (x) = {a}, N abc (y) = {b} and N abc (z) = {c}. By Lemma 2.1.13, there exists a confluence S of {x, y, z}. If S is of Type 1, then S ∪ {a, b, c} induces an ISK4, a contradiction. If S is of Type 2, then S ∪ {a, b, c} induces a prism, a contradiction. Hence, G[N i (u)] contains no triangle.

  1.13, there exists a confluence S of {x, y, z}. If S is of Type 1, S ∪{a, b, c, d} induces an ISK4, a contradiction. If S is of Type 2, S ∪{a, b, c} induces an ISK4, a contradiction. Therfore, G[N i (u)] contains no C 4 . By Claim 2.1.18, the girth of N i (u) is at least 5 for i ≥ 1. By Theorem 2.1.4, χ(G[N i (u)]) ≤ 3. By Lemma 2.1.14, χ(G) ≤ 6, which completes the proof. Lemma 2.1.19. Let G be a graph in C 2 . Then χ(G) ≤ 12.

Claim 2 . 1 . 20 .

 2120 No vertex in N i-1 (u) is adjacent to both b and c. Proof. Suppose there is a vertex y ∈ N i-1 (u) adjacent to both b and c. Since {x, y, b

Claim 2 .

 2 1.23. t has some neighbor in P yz .

Lemma 2 . 1 . 25 .

 2125 Let G be the line graph of a graph H with maximum degree three. Then χ(G) ≤ 4.

Lemma 2 . 1 . 26 .

 2126 Let G be a rich square. Then χ(G) ≤ 4.

Figure 3 . 1 : 6 Figure 3 . 1 Lemma 3 . 3 . 5 .

 31631335 Figure 3.1: Graph G 5 with ω(G 5 ) = 5 and χ(G 5 ) = 6

Lemma 3 . 4 . 1 .

 341 Let D be a class of graphs and B ⊆ D be the set of its basic graphs such that every graph G ∈ D has a 2-join decomposition tree. Furthermore, there exists an integer d ≥ 2 such that every basic graph in D has property P(d). Then for every graph G ∈ D, rwd(G) ≤ d.

  Figures 3.2 and 3.3 are the example of an extended nontrivial basic graph G and its characteristic tree F G (the bold edges are the edges of flat paths in S). Note that each node in F G corresponds to a subset S v of V (G), they are all disjoint, each of them induces a flat path in G and V (G) = ∪ v∈F G S v .

Figure 3 . 2 :

 32 Figure 3.2: An extended nontrivial basic graph G with a set of flat paths.

{3, 4 ,Figure 3 . 3 :

 433 Figure 3.3: The characteristic tree F G for graph G in Figure 3.2.

Figure 3 . 4 :

 34 Figure 3.4: The rank-decomposition for graph G in Figure 3.2.

Proposition 3 . 4 . 4 .

 344 The above constructed rank-decomposition (T, L) of G has width at most 3.

2 .

 2 If v is an internal node in F G and v 1 , . . . , v k are its children. Let (T i , L i ) (i = 1 . . . k) be the rank-decompositions of G[X v i ]. Let e be an edge of T v . If e is an edge of T i then the width of e is at most 3 by induction. Otherwise, e corresponds to one of the following situations:

Lemma 3 . 4 .

 34 2 is true because of the Propositions 3.4.3 and 3.4.4.

  Figure 4.1.

Figure 4 . 1 :

 41 Figure 4.1: A claw-free graph where every connected order is bad.

Figure 4 . 2 :

 42 Figure 4.2: Some graphs

2

 2

  and 4.3, all the straight lines are edges, all the curved lines are paths of length ≥ 1. In Figure4.2:

Figure 4 . 3 :

 43 Figure 4.3: List of obstructions

Claim 4 . 3 . 3 .

 433 If π(a) = 1 or π(a) = 2, then every vertex v ∈ K satisfies v > b. Since π(a) = 1 or π(a) = 2, we have π(b ) = π(a) by Lemma 4.2.11 and the parity of P . Suppose that there exists a vertex v ∈ K with v < b. Then, there exists a vertex u ∈ L such that u < b, for otherwise G <b is disconnected (v and a are in different components). Since by Claim 4.3.2, π(u) = π(b) and u has no neighbor with color π(b), we have π(u) < π(b). But then, when the greedy algorithm visits b, color π(u) is available for b (because π(u) = π(a) = π(b ) and u is complete to R), a contradiction. This proves Claim 4.3.3. By Claim 4.3.3, if π(a) = 1 or π(a) = 2, then π(b) = 3π(a) by the parity of P . Since O is connected, in fact for every vertex v in V (G) \ V (P ), v > b. So, when the greedy algorithm visits G \ P , the first vertex receives color 1 or 2, and it gives exactly the same colors as the greedy algorithm starting with color 1 or 2 applied to (G \ P , O \ P ). Hence, by Lemma 4.2.1, we see that O is a good order for G, a contradiction. Hence, π(a) ≥ 3.

  2.13 that P is well ordered. We therefore have π(b ) = π(a) ≥ 3 (if b = a) or π(b ) = 2 by the parity of P . This implies π(b) = 1, contradicting Claim 4.3.2.

  1 , . . . , a k } and S b = {b 1 , . . . , b k } are two cliques. • K a = C a ∪ S a and K b = C b ∪ S b are two cliques (C a and C b may be empty).• If C a = ∅, then S a is a clique cutset of G. • If C b = ∅, then S b is a clique cutset of G.

3 . 4 . 5 . 6 .

 3456 Let a ∈ S i , b ∈ S i+1 and c ∈ S j . If a is not adjacent to b then {v i , v i-1 , a, v i+1 , b} induces a gem, a contradiction. If a is adjacent to c then {a, c, v i , v i+1 , . . . , v j-1 , v j } induces F 3 or a gem, a contradiction.Let a ∈ R i and b ∈ R j . If a is adjacent to b then {a, b, v i , v i+1 , . . . , v j , v j+1 } contains F 3 or a gem, a contradiction. Let a ∈ S i and b ∈ R i . If a is not adjacent to b then {v i , v i-1 , a, v i+1 , b} induces a gem, a contradiction. S i is also complete to R i-1 by symmetry. Let a ∈ S i and b ∈ R j . If a is adjacent to b then {a, b, v i , v i+1 , . . . , v j , v j+1 } contains F 3 or a gem, a contradiction. If a is not adjacent to b then {a, b}∪V (H) contains F 1 , F 5 , F 6 or a fish (a special case of F 11 ). So, R j = ∅. 7. Let a ∈ R i , b ∈ R i+1 and c ∈ R i+2 . If a is not adjacent to b, then {a, b} ∪ V (H) induces F 2 , a contradiction. If a is adjacent to b, then {v i+1 , v i , a, b, v i+2 } induces a gem, a contradiction. So, R i+1 = ∅. If a is not adjacent to c, then {a, c} ∪ V (H) induces F 3 . If a is adjacent to c, then {a, c, v i , v i+1 , v i+2 , v i+3 } induces either F 3 or F 4 , a contradiction. So, R i+2 = ∅.The proof for R i-2 and R i-1 is similar.

Lemma 4 . 4 . 5 .

 445 G does not contain a 4-wheel.Proof. Suppose G contains a 4-wheel consisting of a hole H = v 0 v 1 v 2 v 3 and a vertex x complete to that hole. For i ∈ {0, . . . , 3}, letS i = {u|N (u) ∩ H = {v i-1 , v i , v i+1 }}, R i = {u|N (u) ∩ H = {v i , v i+1 }} and T = {u|N (u) ∩ H = {v 0 , v 1 , v 2 , v 3 }}. Note that x ∈ T .Claim 4.4.6. For i ∈ {0, . . . , 3}, R i = ∅.

Claim 4 . 4 . 7 .

 447 For i ∈ {0, . . . , 3}, S i is complete to T . Let a ∈ S i and b ∈ T . If a is not adjacent to b then {v i-1 , v i-2 , b, v i ,a} induces a gem, a contradiction. This proves Claim 4.4.7. By Lemma 4.4.4, S i is a clique complete to S i+1 and anticomplete to S i+2 . So, G[∪ 3 i=0 S i ] is P 4 -free. Claim 4.4.8. V (G) = T ∪ 3 i=0 S i ∪ V (H).

  , 4.4.18 and 4.4.19, H ∪ C a ∪ C b ∪ C c ∪ C d is a flower in G, contradicting Lemma 4.3.13.Case 2: G does not contain bracelet. There exists an odd prism system in G as in the description, choose such a prism system H with maximum value of k. LetC a = {v ∈ V (G) \ V (H)|N (v) ∩ S a = ∅} and C b = {v ∈ V (G) \ V (H)|N (v) ∩ S b = ∅}. Claim 4.4.20. Let v ∈ V (G) \ V (H)be a vertex has some neighbor {a, b} in the interior of some path P i (a is closer to a i than b in P i ). Then two paths a i P i a and b i P i b are of even length ≥ 2.Otherwise G contains F 2 , F 3 or F 9 , a contradiction. This proves Claim 4.4.20.Claim 4.4.21. If v ∈ V (G) \ V (H)has some neighbors in P i , then all path P j 's are flat for any j = i.Otherwise G contains F 10 , a contradiction. This proves Claim 4.4.21. W.l.o.g, suppose that P 1 is the only path among P i 's which might not be flat. For some m ≥ 0, let {c 1 , d 1 }, . . . , {c m , d m } be all the possible positions in P 1 to which a vertex v ∈ V (G)\V (H) can be adjacent (c i d i is an edge; all vertices are listed in order from a 1 to b 1 ). For i ∈ {1, . . . , m}, letK i = {v ∈ V (G) \ V (H)|N (v) ∩ {c i , d i } = ∅}.Claim 4.4.22. C a is a clique complete to S a ; C b is a clique complete to S b and K i is a clique complete to {c i , d i } for i ∈ {1, . . . , m}. Follows directly from Lemma 4.4.4. This proves Claim 4.4.22. Claim 4.4.23. a 1 P 1 c 1 and d m P 1 b 1 are flat paths of even length ≥ 2; d i P 1 c i+1 is a flat path of odd length ≥ 3 for i ∈ {1, . . . , m -1}. Follows from Claim 4.4.20. This proves Claim 4.4.23. Claim 4.4.24. If C a and C b = ∅, S a , S b , {c i , d i } are clique cutsets in G for i ∈ {1, . . . , m}.

  Detecting an ISK4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . Proof of Lemma 2.2.2 . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 χ-bounding function . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . .

	3 Even-hole-free graphs
	3.1 1

Introduction 1 Basic notions 1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Perfect graphs and χ-boundedness . . . . . . . . . . . . . . . . . . . . 1.3 Some kinds of decomposition and graph operations . . . . . . . . . . 1.4 Some particular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 2 IKS4-free graphs 2.1 Chromatic number of ISK4-free graphs . . . . . . . . . . . . . . . . . 2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Proof of Theorem 2.1.7 . . . . . . . . . . . . . . . . . . . . . . 2.1.4 Proof of Theorem 2.1.8 . . . . . . . . . . . . . . . . . . . . . . 2.1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Antennas and cables . . . . . . . . . . . . . . . . . . . . . . . 2.2.4

  For some graph H, we say that graph G contains H as an induced subgraph if there exists X ⊆ V such that G[X] is isomorphic to H. A graph is H-free if it does not contain H as an induced subgraph. Given a family of graphs H, a graph G is said to be H-free if it is H-free for every H ∈ H. A class of graphs is hereditary if it is closed under taking induced subgraphs. It is clear that a graph class defined by forbidding a list of graphs is hereditary. Since hereditary graph classes are the main focus of our work, for convenience, we often say that a graph G contains a graph H if G contains H as an induced subgraph.

  , c} does not induce K 4 , xy / ∈ E. If ya ∈ E, {a, b, c, x, y} induces a 4-wheel, a contradiction. Hence, ya / ∈ E. We also have yd / ∈ E by symmetry. We claim that N C (y) = {b, c}. Suppose that y has some neighbor in P * . If y has exactly one neighbor in P * , then {y} ∪ C induces an ISK4, a contradiction. If y has exactly two consecutive neighbors in P * , then C ∪ {x, y} \ {c} induces a prism, a contradiction. If y has at least three neighbors in P * , or two neighbors in P * that are not consecutive, then let z be the one closest to a and t be the one closest to d. Then {x, y, b} ∪ zP a ∪ tP d induces an ISK4, a contradiction. So N C (y) = {b, c}. Let z be a vertex in N i-1 (u) which has a neighbor in P * and P yz be an upstairs path of {y, z}. If z has exactly one neighbor in C, then P yz ∪ C induces an ISK4, a contradiction. If z has exactly two consecutive neighbors in C, then P yz ∪ C induces a prism, a contradiction. If z has at least three neighbors in C or two neighbors in C which are not consecutive, let t, w be the ones closest to b, c in C, respectively. Let Q be the path from t to w in C which contains b. We have that P yz ∪ Q induces an ISK4, a contradiction. ty ∪ {x, b, c} induces an ISK4, a contradiction. So N xbc (t) = {x}. By Lemma 2.1.13, let S be a confluence of {y, z, t}. If S is of Type 1, S ∪ {x, b, c} induces an ISK4, a contradiction. If S is of Type 2, S ∪ {x, b, c} induces a prism, a contradiction. Then xy ∈ E. Symmetrically, xz ∈ E.

By Claim 2.1.20, let y, z be two distinct vertices in N i-1 (u) such that yb, zc ∈ E, yc, zb / ∈ E and P yz be an upstairs path of {y, z}. Claim 2.1.21. xy, xz ∈ E. Proof. Suppose xy / ∈ E. Then xz / ∈ E, otherwise P yz ∪ {x, b, c} induces an ISK4. Let t ∈ N i-1 (u) such that tx ∈ E, let P ty and P tz be upstairs paths of {t, y} and {t, z}, respectively. If tb ∈ E, then tc / ∈ E by Claim 2.1.20, and P tz ∪ {x, b, c} induces an ISK4, a contradiction. If tc ∈ E, then tb / ∈ E by Claim 2.1.20 and P By Claim 2.1.21, yz / ∈ E (for otherwise {x, b, c, y, z} induces a 4-wheel). Claim 2.1.22. N C (y) = {b} and N C (z) = {c}.

  Running time: O(n5 ). An ISK4 is either K 4 , a twin wheel or contains a claw. Proof of Theorem 2.2.1 by Lemma 2.2.2. We describe an algorithm to detect an ISK4 in G as follows. First, we check if there is a K 4 or a twin wheel in G. Checking if there exists a K 4 takes O(n 4 ). Checking if there is a twin wheel in G can be done as follows: list all 4-tuples (a, b, c, d) of vertices in G such that they induce a K 4 \ e (a graph obtained from K 4 by removing one edge, usually called a diamond ) where ad / ∈ E(G); for each tuple, check if a and d are connected in G\((N [b]∪N [c])\{a, d}). Since we have O(n 4 ) such tuples, this can be done in O(n 6

	Lemma 2.2.3.

  Let c be the center of the only claw in H. Let x , y , z be three neighbors of c such that x (y , z ) is the one closest to x (y, z, respectively) in H. Denote by P x , P y , P z the paths from x to x , y to y , z to z in H, respectively. Let v ∈ G \H. The following is true:

v cannot have neighbors in both P x , P y , P z . If v does, N H (v) = {x , y , z , c} or N H (v) = {x , y , z }, otherwise (H \{c, t})∪ {v} is a graph connecting x, y, z which is smaller than H, where t is one of {x , y , z }, a contradiction. If N H

  If v has two neighbors in P x , let t be the neighbor of v in P z which is closest to y. In this case, {u, v, y} ∪ P x ∪ tP z z induces an ISK4 in G. Therefore, v has exactly one neighbor in P x and one neighbor in P y . But now, {u, v} ∪ H induces an ISK4 in G. Now, v is adjacent to y. Since v has at most two neighbors in P x ∪ {y} and two neighbors in P z ∪ {y}, v has exactly one neighbor in P x and one neighbor in P

z . If v is not adjacent to x , let t be the neighbor of v in P x . Now {u, v, y} ∪ P z ∪ xP x t induces an ISK4 in G. Therefore, N H

  Theorem 4.1.3. Let G be a claw-free graph. Then G is good if and only if G does not contain any obstruction as an induced subgraph. Equivalently, a claw-free graph is minimally bad if and only if it is an obstruction.

	F 1	F 2	F 3	F 4
	F 5	F 6	F 7	F 8
	F 9	F 10	F 11	F 12

CONTRIBUTION

Bibliography

Theorem 3.1.1 follows immediately from the above corollary since we can greedily color G in the reverse order of that nice elimination order using at most ω(G) + 1 colors. Therefore, the rest of this section is to devoted to the proof Lemma 3.3.2. Lemma 3.3.4. Let G be a special basic even-hole-free graph with no star cutset associated with (C G , F G ) and G is neither a clique nor a hole. Let P be a flat path of length at least 2 in G. We denote by u 1 , u 2 the two ends of P .

• If N (u 1 ) \ V (P ) is a clique, set K 1 = N (u 1 ) \ V (P ), otherwise set K 1 = ∅.

• If N (u 2 ) \ V (P ) is a clique, set K 2 = N (u 2 ) \ V (P ), otherwise set K 2 = ∅.

Then G \ F G admits a nice elimination order v 1 ,. . . , v k , where Q P is in the end of this order (i.e. Q P = {v k-|Q P |+1 , . . . , v k }).

Proof. We prove the lemma when G is a long pyramid or an extended nontrivial basic graph. In fact, since the proof for a long pyramid can be treated almost similarly, we only show here the proof in the case where G is an extended nontrivial basic graph. Suppose that V (G) = V (H) ∪ {x, y}, where H is the line graph of a tree. We may assume the followings:

1. P is a maximal flat path in G (two ends of P are of degree ≥ 3).

If the lemma is true when P is a maximal flat path then it is also true for all subpaths of P , because Q P admits a perfect elimination order (an order of vertices in which the neighborhood of a vertex induces a clique at the time it is eliminated) where a fixed subpath of P is in the end of this order.

All the vertices in

Observe that the neighborhood of every vertex v in G, except x and y, induces a union of two cliques. Therefore, if v ∈ C G , it must have a neighbor of degree 2 in F G , then its neighborhood in G \ F G actually induces a clique and it can be eliminated at the beginning of our order.

Every vertex in

Indeed, by the assumption 2, C G ⊆ {x, y} ∪ Q P . If a vertex v ∈ G \ (F G ∪ Q P ) has two neighbors in C G , then it must have a neighbor u ∈ (C G ∩ Q P ) \ {x, y}. By the definition of C G , v must be a vertex in F G since it is the only neighbor of degree 2 of u, a contradiction to the choice of v.

Let us first forget about the flat path P and the restriction of putting all the vertices of Q P in the end of the order. We will show how to obtain a nice elimination order for G \ F G in this case. We choose an arbitrary extended clique K R in H and call it the root clique. For each other extended clique K in H, there exists a vertex v ∈ K whose removal separates the root clique from K \ v in H, we call it B-vertex. We call a node E-vertex if it is adjacent to x or y. Note that in each extended clique K, we have exactly one B-vertex and at most one E-vertex (by Lemma 3.2.2). For the root clique K R , we also add a new vertex r adjacent to all the vertices of K R , and let it be the B-vertex for K R . Now, if we remove every edge in every extended clique, except the edges incident to its B-vertex, we obtain a tree T H rooted at r. Note that V (T H ) = V (H) ∪ {r}. We specify the nice elimination order for G where all the vertices in V (K R ) are removed last (we do not care about the order of eliminating r, this vertex is just to define an order for V (G) more conveniently). Let O T be an order of visiting V (T H ) \ (V (K R ) ∪ {r}) satisfying:

• A node u in T H is visited after all the children of u.

• If u is a B-vertex of some extended clique K, the children of u must be visited in an order where the E-vertex in K (if it exists) is visited last.

Let us introduce some notions with respect to orders first. Let O 1 = v 1 , . . . , v k and O 2 = u 1 , . . . , u t be two orders of two distinct sets of vertices. We denote by O 1 ⊕ O 2 the order v 1 , . . . , v k , u 1 , . . . , u t . If S is a subset of vertices of some order O 1 , we denote by O 1 \ S the order obtained from O 1 by removing S. Let u be a vertex, we also denote by u the order of one element u.

Let O K R be an arbitrary elimination order for the vertices in K R . Now the elimination order for

We prove that this elimination order is nice. Indeed, let u be a vertex of order O T , u / ∈ F G . If u is not an E-vertex, then its neighborhood at the time it is eliminated is either a subclique of some extended clique (if its parent is a B-vertex) or a single vertex which is its parent. If u is an E-vertex, since it is eliminated after all its siblings (the nodes share the same parent), its neighborhood consists of only two vertices: its parent and x (or y). And by assumption 3, at most one of these two vertices is in C G , so u is almost simplicial. Now when x is removed in this order, it has at most two neighbors: one is y and one is possibly a vertex in K R , also not both of them are in C G , so x is almost simplicial. Vertex y has at most one neighbor at the time it is eliminated. And finally, K R is a clique so any eliminating order for K R at this point is nice. Now we have to consider the flat path P , and put all the vertices of Q P in the end of the elimination order. There are two cases:

• P is a flat path not containing x and y.

In this case, both K 1 and K 2 are non-empty. The graph obtained from G by removing V (P ) ∪ {x, y} contains two connected components H 1 , H 2 , where H i (i = 1, 2) is the line graph of a tree. By considering K i as the root clique of H i , from the above argument, we obtain two elimination orders O 1 , O 2 for H 1 \ K 1 and H 2 \ K 2 . Now, all the vertices not yet eliminated in G are in {x, y} ∪ Q P . We claim that at least one of x, y has at most two neighbors in the remaining graph. Indeed, otherwise x and y both have at least three neighbors, implying that they both have neighbors in K 1 and K 2 , which contradicts Lemma 3.2.2. Suppose x has at most two neighbors, in this case we eliminate x first, then y. Note that x and y are both almost simplicial in this elimination order, since they have at most two neighbors (not both of them in C G according to assumption 3) at the time they were eliminated. Finally, choose for Q P a perfect elimination order O Q . Now the nice elimination order for

The graph H obtained by removing V (P ) ∪ {y} from G is the line graph of a tree. We consider K 2 as the root clique of this graph. From above argument, we have a nice elimination order O H for V (H )\K 2 . Now all the vertices left in G are in {y} ∪ Q P . Observe that y has at most two neighbors in the remaining graph (x and possibly a vertex in K 2 ), therefore y is almost simplicial and can be eliminated. Note that x has no neighbor in K 2 , since if u ∈ K 2 is adjacent to x, then {u} ∪ N (u) is a star cutset in G separating P * from the rest of the graph (P * is non-empty since the length of P is at least two). Finally, choose for Q P a perfect elimination order O Q . Now the nice elimination order for

Proof of Lemma 3.3.2. By Lemma 3.2.6, G has an extreme 2-join decomposition tree T G . Now, for every node (G , S ) of T G , G is a special connected even-hole-free graph with no star cutset associated with (C G , F G ) (by Lemmas 3.2.4 and 3.3.1). Now we prove that for every node (G , S ) of T G , G satisfies Lemma 3.3.2. This implies the correctness of Lemma 3.3.2 since the root of T G corresponds to G.

First, we show that for every leaf node (G , S ) of T G , G satisfies Lemma 3.3.2. If G is a clique then any elimination order of G \F G is nice. If G is a hole, there exists a vertex v such that one of its neighbors is not in C G , then v can be eliminated first. each vertex a color equal to the smallest positive integer not used by its neighbours already colored. Lemma 4.2.1. When applied to a good graph, the greedy coloring algorithm starting with color 2 produces an optimal coloring.

Proof. The coloring produced by this algorithm is the same as the coloring produced by the connected order obtained from O by swapping the first two vertices. Hence it is optimal.

For the rest of this section, G is a minimally bad graph with a bad order O = [v 1 , . . . , v n ]. Note that for any set S V (G), if O[S] is a connected order then it produces an optimal coloring for G

Proof. Follows directly from the fact that O is a bad order and that G is a minimally bad graph.

Proof. The conclusion is true for y = v n . Because by the minimality of G, we have

Proof. Otherwise, π(v n ) ≤ 3, so by Lemma 4.2.2, χ(G) ≤ 2, so G is bipartite, a contradiction to Theorem 4.1.2. Lemma 4.2.5. For every vertex v ∈ V (G), G ≤v , G ≥v , G <v and G >v are connected. In particular, G is connected.

Proof. For G ≤v , it comes from the definition of connected orders.

Suppose

and let O i be the order O restricted to V (G i ). For every i ∈ {1, . . . , k} and for every vertex

The proof is the same for G <v and G >v (note that we view the empty graph as a connected graph).

is not connected: v 1 and min(C) are in different components, a contradiction to Lemma 4.2.5.

It is sometimes convenient to view G and O as an oriented graph D G , obtained from G by orienting from u to v every edge uv such that u < v. We therefore use the notion of in-neighbor, outneighbor, source and sink in G (a source in G is a vertex with no in-neighbor in D G and a sink in G is a vertex with no outneighbor in D G ). Lemma 4.2.9. G has a unique source that is v 1 and a unique sink that is v n .

Proof. Obviously, v 1 is a source and v n is a sink. If G has two sources u < v, then G ≤v is disconnected (u and v are in two distinct components), a contradiction to Lemma 4.2.5. If G has two sinks u < v, then G ≥u is disconnected (u and v are in two distinct components), a contradiction to Lemma 4.2.5. Lemma 4.2.10. Let v be a vertex of degree 2 in G and let b < a be its neighbors. One and exactly one of the following outcome occurs:

Lemma 4.2.13. If P = a . . . b is a flat path in G then either it is well ordered, or the source v 1 is an internal vertex of P and aP v 1 , v 1 P b are both well ordered. In particular, there exists at most one maximal flat path in G that is not well ordered.

Proof. This follows from Lemmas 4.2.10 and the definition of connected orders.

v < s 1 . We then have s 1 < a 1 for otherwise, G <s 1 is disconnected (a 1 and v are in different components). So, π(s 1 ) = 1 (since no vertex smaller than s 1 in K has color 1 by Lemma 4.2.14). This is a contradiction because π(a 1 ) = 1.

First, π(s 1 ) = 1 since if π(s 1 ) ≥ 2, there exists a vertex u ∈ K such that u < s 1 and π(u) = 1. So, s 1 < a 1 for otherwise G <s 1 is disconnected. Since by Lemma 4.2.14 no vertex smaller than s 1 in K receives color 2, s 1 receives color 2, a contradiction. By Lemma 4.2.14, π(v) = 2 and because of

Forbidden structures of minimally bad graphs

Throughout this section, let G be a minimally bad claw-free graph that is not an obstruction.

A graph H is a cap in G if:

• K is a clique disjoint from P , K = L ∪ R ∪ C such that L, R, C are non-empty.

• P is a flat path in G of odd length ≥ 1 with two ends a, b.

• a is complete to L, b is complete to R.

• These are the only edges in H.

Proof. Suppose G contains a cap H and K, L, R, C, P , a, b are defined as in the definition of a cap. Let a and b be the vertices adjacent to a and b in P , respectively. By Lemma 4.2.12, we may assume up to symmetry that b = max(V (P )).

• These are the only edges in H.

Lemma 4.3.4. G does not contain an even birdcage.

Proof. Suppose G contains an even birdcage H, with the notation as in the definition of an even birdcage. Up to symmetry, we suppose

for some i ∈ {1, . . . , k}, then v < b k follows from Lemma 4.2.12. Otherwise, G >max(Sa) is disconnected (v and b k are in different components), a contradiction to Lemma 4.2.5. This proves Claim 4.3.5.

For all i ∈ {1, . . . , k}, let a i , b i be the vertices in P i adjacent to a i , b i respectively. By Lemma 4.2.14 applied to S b , we consider the following two cases:

Then, by the parity of P and Lemma 4.2.11, we also have π(a i ) = 1. By Lemma 4.2.13, we may assume up to symmetry that P 1 is well ordered. Since π(a 1 ) = 1 and since color 1 does not appear in S a , a 1 must have an in-neighbor in C a with color 1. This proves Claim 4.

Then, by the parity of P and Lemma 4.2.11, we also have π(a i ) = 2. By Lemma 4.2.13, up to symmetry, we may assume that P 1 is well ordered. Suppose that A graph H is an odd birdcage in G if:

• P 1 is a path of odd length ≥ 3 with two ends a 1 , b 1 .

• ∀i ∈ {2, . . . , k}, P i is a flat path of odd length ≥ 3 with two ends a i , b i .

• All a i 's and b i 's are distinct.

• • If C a = ∅, then S a is a clique cutset of G.

• For i ∈ {1, . . . , m}, c i 's, d i 's are vertices of P 1 such that:

-They appear in P 1 in the following order:

-∀i ∈ {1, . . . , m}, c i d i is an edge.

a 1 P 1 c 1 and d m P 1 b 1 are flat paths of even length ≥ 2.

-∀i ∈ {1, . . . , m -1},

-∀i ∈ {1, . . . , m}, K i is a non-empty clique complete to {c i , d i }.

-∀i ∈ {1, . . . , m}, {c i , d i } is a cutset of G.

• These are the only edges in H.

• No vertex in ∪ k i=1 V (P i ) has a neighbor in G \ H. Lemma 4.3.9. G does not contain an odd birdcage.

Proof. Suppose G contains an odd birdcage H as in the definition of an odd birdcage. For i ∈ {1, . . . , k}, let a i , b i be the neighbors of a i , b i in P i respectively. For j ∈ {1, . . . , m}, let c j , d j be the neighbors of c j , d j in P 1 \ {c j , d j } respectively. Let x = max(∪ m i=1 V (P i )). By Lemma 4.2.12, we may assume that x = d i for some i ∈ {1, . . . , m} or x = b j for some j ∈ {1, . . . , k}.

Case 1: x = d i for some i ∈ {1, . . . , m}.

By Lemma 4.2.15 applied to the cutset {c i , d i }, there exist some vertices u ∈ K i , p, q / ∈ K i such that u, p, q is a triangle and π Then for every i ∈ {2, . . . , k}, π(a i ) = 2 by the parity of the flat paths. Also, for every i ∈ {2, . . . , k}, b i < b i since otherwise b i has color ≥ 2 and there must exist in K b some in-neighbor of b i having color 1, contradicting Lemma 4.2.14. By Lemma 4.2.13, we may assume that P 3 is well ordered. Since π(a 3 ) = 2, we have π(a 3 ) = 1. So, π(a 2 ) = 1, and since π(a 2 ) = 2, we have a 2 < a 2 . So, P 2 is not well ordered. By Lemma 4.2.13, the source of G, v 1 , is an internal vertex of P 2 and v 1 P 2 a 2 and v 1 P 2 b 2 are both well ordered. If a 2 < b 2 , then π(a 2 ) = 1, a contradiction. Hence, b 2 < a 2 and π(b 2 ) = 2. The vertex v that comes just after b 2 in O cannot be a 2 , because then, again, we would have π(a 2 ) = 1. Hence, v is in K b and receives color 1, a contradiction to Lemma 4.2.14.

Suppose now that π(b i ) = 2 ∀i ∈ {1, . . . , k}. Then for every i ∈ {2, . . . , k}, π(a i ) = 1 by the parity of the flat paths. Similarly, we can prove π(d i ) = π(c i ) = 1 for all i ∈ {1, . . . , m}, and therefore π(a 1 ) = 1.

We must have a vertex of color 1 in C a , otherwise a i < a i for every i ∈ {1, . . . , k}. Also, for some 1 If

A graph H is a flower in G if:

• For i ∈ {1, . . . , k}, P i is a flat path of odd length ≥ 3 with two ends a i and b i .

• For i ∈ {1, . . . , m}, Q i is a flat path of odd length ≥ 3 with two ends c i and d i .

• P ac is a flat path of even length ≥ 2 with two ends a 0 and c 0 .

• P bd is a flat path of even length ≥ 2 with two ends b 0 and d 0 .

• These are the only edges in H.

-They appear in the following clock-wise order: a 0 , b 0 , . . . , a k , b k .

-For ∀i ∈ {0, . . . , k}, a i is adjacent to b i .

-For ∀i ∈ {0, . . . , k}, the path in I from b i to a i+1 is a flat path of length ≥ 2 (the subscript is taken modulo (k + 1)).

• For i ∈ {0, . . . , k}, K i is a non-empty clique complete to {a i , b i }.

• For i ∈ {0, . . . , k}, {a i , b i } is a cutset of G.

• These are the only edges in H.

• No vertex in G \ H has a neighbor in I. Proof. Suppose G contains a sun H as in the definition. For i ∈ {0, . . . , k}, let a i , b i be the vertices of degree 2 adjacent to For our proof, we need results from [START_REF] Hertz | Connected sequential colorings[END_REF]. A graph G is a parity graph if for every pair u, v ∈ V (G), all induced paths from u to v have the same parity. A graph is distance-hereditary if for every pair u, v ∈ V (G), all induced paths from u to v have the same length. Clearly, every distance-hereditary graph is a parity graph. A graph is chordal if it contains no hole. Theorem 4.4.1 (see [3]). Every gem-free chordal graph is a distance-hereditary graph and therefore a parity graph. Theorem 4.4.2 (see [START_REF] Hertz | Connected sequential colorings[END_REF]). Every fish-free parity graph is good.

Throughout the rest of this section, let G be a minimally bad claw-free graph that is not an obstruction. Our goal is to prove that this implies a contradiction, thus proving Theorem 4.1.3. Suppose there exists some vertex v ∈ V (G) \ (T ∪ 3 i=0 S i ∪ V (H)) and v has some neighbors in T ∪ 3 i=0 S i ∪ V (H). If v has a neighbor in V (H), then v ∈ T ∪ 3 i=0 S i , a contradiction. If v has a neighbor u in S i for some i but no neighbor in V (H), then {u, v, v i-1 , v i+1 } forms a claw, a contradiction. If v has a neighbor u in V (T ) but no neighbor in V (H), then {u, v 0 , v 2 , v} forms a claw, a contradiction. This proves Claim 4.4.8.

We have G[T ] is P 4 -free (otherwise v 0 and some

, then G is P 4 -free and therefore is good by Theorem 4.1.1, a contradiction.

A twin wheel is a graph consisting of a hole H and a vertex x has three consecutive neighbors on H (see Figure 4.2). Note that this definition of a twin wheel was already mentioned in Section 2.2. Lemma 4.4.9. G does not contain a twin wheel.

Proof. Suppose G contains a twin wheel consisting of a hole H = v 0 . . . v k and a vertex x that has three neighbors on H: v 0 , v 1 , v 2 . We can assume that H is an even hole since otherwise G contains F 1 . For i ∈ {0, . . . , k}, let

We consider two cases:

Case 1: There exists some vertex y ∈ R j for some j.

Hence, G is a parity graph. Also, G is fish-free because the fish is an obstruction. Therefore, G is good by Theorem 4.4.2, a contradiction.

From now on, by Lemmas 4.4.5 and 4.4.9, the neighborhood of any vertex on a hole in G induces an edge. From now on, we know that that every prism in G is not short, or in another word, its three paths are of length at least 2. Proof. Otherwise, it contains F 7 , a contradiction.

A graph H is a prism system if:

for some k ≥ 3. • ∀i ∈ {1, . . . , k}, P i is a path of length ≥ 2 with two ends a i , b i . All P i 's are disjoint.

• S a = {a 1 , . . . , a k } and S b = {b 1 , . . . , b k } are two cliques.

• These are the only edges in H.

Note that if k = 3 then H is simply a prism. A prism system is even (odd ) if the lengths of all path P i 's are even (odd).

Lemma 4.4.12. G does not contain an even prism.

Proof. Suppose G contains an even prism. Then there exists an even prism system in G as in the description, choose such a prism system H with maximum value of k. Let

Claim 4.4.13. All paths P i 's are flat.

If there exists a vertex v ∈ V (G) \ V (H) which has some neighbors {a, b} in the interior of some path P i , then G contains F 2 , F 3 or F 8 , a contradiction. This proves Claim 4.4.13. Claim 4.4.15. We have the followings:

We prove only the first statement, the second is similar. Suppose that there exists a path P from some vertex in C a to some vertex in C b . The length of P is even otherwise G contains F 7 , then H ∪ P is a bigger even prism system, a contradiction to the choice of H. This proves Claim 4. A bracelet (see Figure 4.2) has six paths of length ≥ 2: two paths in the sides are of even length; the other four paths are of odd length.

A graph H is a bracelet system if:

• For i ∈ {1, . . . , k}, P i is a path of odd length ≥ 3 with two ends a i and b i .

• For i ∈ {1, . . . , m}, Q i is a path of odd length ≥ 3 with two ends c i and d i .

• P ac is a path of even length ≥ 2 with two ends a 0 and c 0 .

• P bd is a path of even length ≥ 2 with two ends b 0 and d 0 .

• All path P i 's, Q i 's, P ac , P bd are disjoint.

• S a = {a 0 , . . . , a k } and S b = {b 0 , . . . , b k } are cliques.

• S c = {c 0 , . . . , c m } and S d = {d 0 , . . . , d m } are cliques.

• These are the only edges in H. Proof. Suppose G contains an odd prism. We consider the following cases: Case 1: G contains a bracelet. Then there exists a bracelet system in G as in the description, choose such a system H with maximum value of k

Note that if

Claim 4.4.17. All the paths P i 's, Q i 's, P ac , P bd are flat.

Suppose there is some vertex v ∈ V (G) \ V (H) has some neighbor in the interior of one of these paths. If v has some neighbor on P ac or P bd , then G contains F 2 , F 3 or F 9 , a contradiction. If v has some neighbor on some P i or Q i , then G contains F 2 , F 3 , F 9 or F 10 , a contradiction. This proves Claim 4.4.17. Otherwise, there is a path from a vertex in K i to some vertex in K j , for some j = i, so G contains a prism, a contradiction. This proves Claim 4. To prove Theorem 4.1.3, we are left to prove that every obstruction is a minimally bad claw-free graph. Suppose that it is not true for some graph F in the list of obstructions. Since F is bad (as we already specify a bad order for every obstruction), F must contain a minimally bad claw-free graph F as an induced subgraph. Since every minimally bad claw-free graph is an obstruction, F is also an obstruction. However, it is easy to check that there do not exist two obstructions in our list such that one contains the other as an induced subgraph, a contradiction.

Conclusion

In this chapter, we give the characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs. Note that the arguments in Sections 4.3 and

Contributions

All the results in this thesis are covered in the following publications:

[I] N.K. Le. Chromatic number of ISK4-free graphs, Graphs and Combinatorics, 33(6): 1635-1646, 2017.

[II] N.K. Le. Detecting an induced subdivision of K 4 , arXiv preprint, submitted. https://arxiv.org/abs/1703.04637

[III] N.K. Le. Coloring even-hole-free graphs with no star cutset, arXiv preprint, submitted.

[IV] N.K. Le, N. Trotignon. Connected greedy colouring in claw-free graphs, arXiv preprint, submitted. 99