Pierre Aboulker

Jørgen Bang-Jensen

Nicolas Bousquet

Pierre Charbit

Frédéric Havet

Frédéric Maffray

Jose Zamora

χ-bounded families of oriented graphs

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

Introduction

What can we say about the induced subgraphs of a graph G with large chromatic number? Of course, one way for a graph to have large chromatic number is to contain a large complete subgraph. However, if we consider graphs with large chromatic number and small clique number, then we can ask what other subgraphs must occur. We can avoid any graph H that contains a cycle because, as proved by Erdős [START_REF] Erdős | Graph theory and probability[END_REF], there are graphs with arbitrarily high girth and chromatic number; but what can we say about trees? Gyárfás [START_REF] Gyárfás | On ramsey covering-numbers[END_REF] and Sumner [START_REF] Sumner | Subtrees of a graph and the chromatic number[END_REF] independently made the following beautiful and difficult conjecture.

Conjecture 1 (Gyárfás [START_REF] Gyárfás | On ramsey covering-numbers[END_REF] and Sumner [START_REF] Sumner | Subtrees of a graph and the chromatic number[END_REF]). For every integer k and tree T , there is an integer f (k, T ) such that every graph with chromatic number at least f (k, T ) contains either a clique of size k, or an induced copy of T .

We can rephrase this conjecture, using the concept of χ-bounded graph classes introduced by Gyárfás [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF]. A class of graph G is said to be χ-bounded if there is a function f such that χ(G) f (ω(G)) for every G ∈ G; such a function f is called a χ-bounding function. For instance, the class of perfect graphs is χ-bounded with f (k) = k as a χ-bounding function.

For a graph H, we write Forb(H) for the class of graphs that do not contain H as an induced subgraph. For a class of graphs H , we write Forb(H ) for the class of graphs that contain no member of H as an induced subgraph. As we have remarked, Forb(H) is not χ-bounded when H contains a cycle. The conjecture of Gyárfás and Sumner (Conjecture 1) asserts that Forb(T ) is χ-bounded for every tree T . In fact, an easy argument shows that the conjecture is equivalent to the following one .

Conjecture 2. Forb(H) is χ-bounded if and only if H is a forest.

There are not so many cases solved for this conjecture, let us recall the main ones.

• Stars: Ramsey's Theorem implies easily that Forb(K 1,t ) is χ-bounded for every t.

• Paths: Gyárfás [START_REF] Gyárfás | Problems from the world surrounding perfect graphs[END_REF] showed that Forb(P) is χ-bounded for every path P.

• Trees of radius 2: using the previous result, Kierstead and Penrice [START_REF] Kierstead | Radius two trees specify χ-bounded classes[END_REF] proved that Forb(T ) is χ-bounded for every tree T of radius two (generalizing an argument of Gyárfás, Szemerédi and Tuza [START_REF] Gyárfás | Induced subtrees in graphs of large chromatic number[END_REF] who proved the triangle free case). This result is proved using a result, attributed to Hajnal and Rödl (see [START_REF] Kierstead | Radius two trees specify χ-bounded classes[END_REF]) but apparently denied by Hajnal (see [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF]), stating that Forb({T, K n,n }) is χ-bounded for every tree T and every integer n.

• Subdivision of stars: it is a corollary of the following topological version of Conjecture 1 established by Scott [START_REF] Scott | Induced trees in graphs of large chromatic number[END_REF]: for every tree T and integer k, there is g(k, T ) such that every graph G with χ(G) > g(k, T ) contains either a clique of size k or an induced copy of a subdivision of T .

More generally, if H is a finite class of graphs, then Forb(H ) is χ-bounded only if H is a forest, and Conjecture 2 states that the converse is true. In contrast, there are infinite classes of graphs H containing no trees that are χ-bounded. A trivial example is the set of odd cycles, since graphs with no (induced) odd cycles are bipartite. Another well-known example are Berge graphs which are the graphs with no odd holes and no odd anti-holes as induced subgraphs. An induced cycle of length at least 4 is a hole. An induced subgraph that is the complement of a hole is an antihole. A hole or antihole is odd (resp. even) if it has a odd (resp. even) number of vertices. The celebrated Strong Perfect Graph Theorem [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF], states that Berge graphs are perfect graphs, i.e. graphs for which chromatic number equals clique number. In other words, the class of Berge graphs is χ-bounded with the identity as bounding function. Many superclasses of the class of Berge graphs are conjectured or proved to be χ-bounded. In fact, Scott and Seymour [START_REF] Scott | Colouring graphs with no odd holes[END_REF] proved that if G is odd-hole-free, then χ(G) 2 3 ω(G) . This upper bound is certainly not tight. Better bounds are known for small values of ω(G). If ω(G) = 2, then G has no odd cycles and so is bipartite. If ω(G) = 3, then χ(G) 4 as shown by Chudnovsky et al. [START_REF] Chudnovsky | K 4 -free graphs with no odd holes[END_REF].

Theorem 3 (Chudnovsky et al. [START_REF] Chudnovsky | K 4 -free graphs with no odd holes[END_REF]). Every odd-hole-free graph with clique number at most 3 has chromatic number at most 4.

The goal of this paper is to extend some results known about Conjecture 1. Let T be a tree for which we know that Conjecture 1 is true, and let D T be a set of orientations of T . Then one can consider the class Forb(D) of oriented graphs that have an orientation without any induced subdigraph in D T . Different sets D T will define different superclasses of Forb(T ), and one can wonder which of these are still χ-bounded. Equivalently, if one defines the chromatic number or clique number of an oriented graph to be that of its underlying graph, one can also talk about a χ-bounded classes of oriented graphs, and we can ask which set of oriented trees, when forbidden as induced subdigraphs, defines χ-bounded classes of oriented graphs. After a section establishing notations and basic tools, we consider oriented stars (i.e. orientations of K 1,n ) and oriented paths (i.e. orientations of paths). Before detailing those results, let us note that in this oriented setting, if we do not demand the subdigraph to be induced, then the problem is radically different. Burr proved that every (k -1) 2 -chromatic oriented graph contains every oriented tree of order k. This was slightly improved by Addario-Berry et al. [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF] by replacing (k -1) 2 by (k 2 /2k/2 + 1). The right bound is conjectured [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF] to be (2k -2).

Oriented stars

We conjecture the following : Conjecture 4. For any oriented star S, Forb(S) is χ-bounded.

For every choice of positive integers k, , we denote by S k, the oriented star on k + + 1 vertices where the center has in-degree k and out-degree . Of course by directional duality the result for S k, implies the result for S ,k . Also, since Forb(S k, ) ⊆ Forb(S k,k ) if k , it suffices to prove the conjecture for S k,k for all values of k.

The cases k = 0 and k = = 1 are not difficult and were previously known (as mentioned in [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF]) but no proof was published. As those proofs are short and interesting, we provide them in Subsection 3.1.

By definition of χ-boundedness, Conjecture 4 can be restated as follows: for every positive integer p, Forb(Or(K p ), S) has bounded chromatic number, where Or(K p ) is the set of orientations of K p (that is, Or(K p ) is the set of all tournaments on p vertices). There are exactly two orientations of K 3 : the directed cycle on three vertices C 3 , and the transitive tournament on three vertices T T 3 . It is not difficult to show that, for any oriented star S, Forb( C 3 , T T 3 , S) has bounded chromatic number. We can even determine the exact value of χ(Forb( C 3 , T T 3 , S)) (Proposition 14). This can be seen as the first step (p = 3) of Conjecture 4. Kierstead and Rödl [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF] proved that Forb( C 3 , S) is χ-bounded. In Theorem 15, we prove the following counterpart : Forb(T T 3 , S) has bounded chromatic number, for every oriented star S. This can be seen as the next step towards Conjecture 4; indeed, by Theorem 6, every orientation of K 4 contains T T 3 as an induced subdigraph, so Forb(T T 3 , S) ⊂ Forb(Or(K 4 ), S). The next step would be to prove that Forb(Or(K 4 ), S) has bounded chromatic number for every oriented star S.

Oriented paths on four vertices

Let us denote by P k the path on k vertices. Since P 2 and P 3 are stars, the next case for paths concerns orientations of P 4 . The graphs with no induced P 4 are known as cographs, and it is well-known that cographs are perfect. In particular, the class of cographs is χ-bounded (or equivalently Forb(Or(P 4 )) is χ-bounded). There are four non-isomorphic orientations of P 4 . They are depicted in Figure 1. In Section 4, we study Forb(P ) when P is a set of orientations of P 4 . Kierstead and Trotter [START_REF] Kierstead | Colorfull induced subgraphs[END_REF] proved that Forb(P + (3)) is not χ-bounded by constructing (T T 3 , P + (3))-free oriented graphs with arbitrary large chromatic number. Gyárfás pointed out that the natural orientations of the so-called shift graphs ( [START_REF] Erdős | On the chromatic number of infinite graphs[END_REF]) are in Forb( C 3 , T T 3 , P + (1, 1, 1)) but may have arbitrarily large chromatic number. Consequently, Forb(P + (1, 1, 1)) is not χ-bounded. See Subsection 4.1.

P + (3) P + (2, 1) P -(2, 1) P + (1, 1, 1)
We believe that {P + (3)} and {P + (1, 1, 1)} are the only non-empty subsets P of Or(P 4 ) such that Forb(P ) is not χ-bounded.

Conjecture 5. Let P be a non-empty subset of Or(P 4 ).

If P = {P + (3)} and P = {P + (1, 1, 1)}, then Forb(P ) is χ-bounded.
We prove this conjecture in the case when P + (3) ∈ P : in Corollary 35, we show that the classes Forb(P + (3), P + (2, 1)), Forb(P + (3), P -(2, 1)), and Forb(P + (3), P + (1, 1, 1)) are χ-bounded. Hence, it remains to prove Conjecture 5 for P ⊆ Forb(P + (2, 1), P -(2, 1), P + (1, 1, 1)). Several results in this direction have been established. Kierstead (see [START_REF] Schmerl | Recursion theoretic aspect of graphs and orders[END_REF]) proved that every ( C 3 , P + (2, 1), P -(2, 1))free oriented graph D can be coloured with 2 ω(D) -1 colours, so in particular Forb( C 3 , P + (2, 1), P -(2, 1)) is χ-bounded. Chvátal [START_REF]Perfectly ordered graphs. In Topics on perfect graphs[END_REF] proved that acyclic P + (2, 1)-free oriented graphs are perfect, so Forb( C , P + (2, 1)) is χ-bounded. Kierstead and Rödl [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF] generalized those two results by proving (but with a larger bounding function) that Forb( C 3 , P + (2, 1)) is χ-bounded. In Subsection 4.2, we make the first two steps towards the χ-boundedness of Forb(P + (2, 1)). We prove χ(Forb( C 3 , T T 3 , P + (2, 1)) = 3 and χ(Forb(T T 3 , P + (2, 1)) = 4.

Definitions, notations and useful facts

Let D be a digraph. If uv is an arc we say that u dominates v and write u → v. Let P = (x 1 , x 2 , • • • , x n ) be an oriented path. We say that P is an (x 1 , x n )-path. The vertex x 1 is the initial vertex of P and x n its terminal vertex. Then we say that P is a directed path or simply a dipath, if x i → x i+1 for all 1 i n -1. An oriented cycle C = (x 1 , x 2 . . . x n , x 1 ) is a directed cycle, if x i → x i+1 for all 1 i n, where x n+1 = x 1 . The directed cycle of length k is denoted by C k .

The digraph D is connected if its underlying graph is connected. It is strongly connected, or strong, if for any two vertices u, v, there is a (u, v)-dipath in D. A strong component U is initial if all the arcs with head in U have their tail in U. We denote by C the class of directed cycles and by S the class of strong oriented graphs.

The chromatic number (resp. clique number) of a digraph, denoted by χ(D) (resp. ω(D)), is the chromatic number (resp. clique number) of its underlying graph. The chromatic number of a class D of digraphs, denoted χ(D), is the smallest k such that χ(D) k for all D ∈ D, or +∞ if no such k exists. If χ(D) = +∞, we say that D has bounded chromatic number. Similarly to undirected graphs, a class of oriented graphs D is said to be χ-bounded if there is a function f such that χ(D) f (ω(D)) for every D ∈ D (such a function f is called a χ-bounding function for the class).

Let F be a digraph and let F be a class of digraphs. A digraph is F-free (resp. F -free) if it does not contain F (resp. any element of F ) as an induced subgraph. In this paper, we study for which classes F of digraphs, the class of F -free digraphs is χ-bounded. Observe that such an F must contain a complete (symmetric) digraph, that is a digraph in which any two distinct vertices are joined by two arcs in opposite direction. Indeed, K k , the complete digraph on k vertices, has chromatic number k, and every induced subdigraphs of a complete digraph is a complete digraph.

In this paper, we consider oriented graphs, which are K 2 -free digraphs. Alternately, an oriented graph may be defined as the orientation of a graph. Note that an F -free oriented graph is an (F , K 2 )-free digraph. We denote by Forb(F ) the class of F -free oriented graphs. We are interested in determining for which class F of oriented graphs, the class Forb(F ) is χ-bounded. To keep notation simple, we abbreviate Forb({F 1 , . . . , F p }) as Forb(F 1 , . . . , F p ), for some strict subset F of Or(H). More generally, for any result proving that a class Forb(G) is χ-bounded, a natural question is to ask for which subsets F of Or(G), the class Forb(F ) is also χ-bounded. For example, the result mentioned in the introduction stating that Forb({T, K n,n }) is χ-bounded for every tree T and every integer n has been generalized to orientations of K n,n and oriented trees : Kierstead and Rödl [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF] proved that for any positive integer n and oriented tree T , the class Forb(DK n,n , T ) is χ-bounded where DK n,n is the orientation of the complete bipartite graph K n,n where all edges are oriented from a part to the other.

Forb(F 1 ∪ • • • ∪ F p ) in Forb(F 1 , . . . , F p ), Forb({F} ∪ F }) in Forb(F, F ),
A tournament is an orientation of a complete graph. The unique orientation of K n (the complete graph on n vertices) with no directed cycles is called the transitive tournament of order n and is denoted T T n . Let tt(D) be the order of a largest transitive tournament in D. Observe that a class of oriented graphs is χ-bounded if and only if there is a function g such that χ(D) g(tt(D)) for every D ∈ D thanks to the following result due to Erdős and Moser [START_REF] Erdős | A problem on tournaments[END_REF].

Theorem 6 (Erdős and Moser [START_REF] Erdős | A problem on tournaments[END_REF]). For every tournament T , tt(T ) 1 + log |V (T )| .

By the above observation, D is χ-bounded if and only if for every positive integer n, D ∩ Forb(T T n ) has bounded chromatic number. Also let us remark that any orientation of K 4 contains a T T 3 , so D ∩ Forb(Or(K 3 )) ⊂ D ∩ Forb(T T 3 ) ⊂ D ∩ Forb(Or(K 4 )). When we are able to prove the result for Or(K 3 )-free oriented graphs and want to extend the result to Or(K 4 )-free ones, an intermediate step is therefore to prove the T T 3 -free case. We will do this in some cases in Section 3 and 4.

For a set or subgraph S of D, we denote by Reach + D (S) (resp. Reach - D (S), the set of vertices x such that is a directed out-path (reap. directed in-path) with initial vertex in S and terminal vertex x.

Let D be a digraph on

n vertices v 1 , . . . , v n . A digraph D is an extension of D if V (D ) can be partitioned into (V 1 , . . . ,V n ) such that A(D ) = {xy | x ∈ V i , y ∈ V j and v i v j ∈ A(D)}.
Observe that some V i may be empty. In particular, induced subdigraphs of D are extensions of D.

To finish this section let us state easy results that we will often use in the proofs. Recall that a k-critical graph is a graph of chromatic number k of which any strict subgraph has chromatic number at most k -1. For a digraph D, δ(D) denotes the minimum degree of the underlying unoriented graph, and ∆ + (D) (resp. ∆ -(D)) denote the maximum out-degree (resp. in-degree).

Proposition 7. If D is a k-critical digraph, then D is connected, δ(D) k -1 and ∆ + (D), ∆ -(D) (k -1)/2.
Theorem 8 (Brooks [START_REF] Brooks | On colouring the nodes of a network[END_REF]). Let G be a connected graph. If G is not a complete graph or an odd cycle, then χ(G) ∆(G).

Forbidding Oriented Stars

In this section, we study the χ-boundedness of Forb(S), for S an oriented star.

Forbidding

S 0, or S 1,1
In [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF], the authors state that the results in this section were already known, but since they give no reference, and the proofs are short, we include them here. As written in the introduction, the fact that Forb(K 1,t ) is χ-bounded follows directly from the following celebrated theorem due to Ramsey.

Theorem 9 (Ramsey [START_REF] Ramsey | On a problem of formal logic[END_REF]). Given any positive integers s and t, there exists a smallest integer r(s,t) such that every graph on at least r(s,t) vertices contains either a clique of s vertices or a stable set of t vertices.

Similarly, it can be used to show that Forb(S 0, ) is χ-bounded.

Theorem 10. Let be a positive integer. If D ∈ Forb(S 0, ), then χ(D) < 2r(ω(D), ).

Proof. Let D be an S 0, -free oriented graph and let s = ω(D). If χ(D) 2r(s, ), then by Proposition 7, D has a vertex v with out-degree at least r(ω, ). Now the out-neighbourhood, N + (v), of v contains no stable set of size , for its union with v would induce an S 0, . Therefore, by Theorem 9, N + (v) contains a clique of s vertices, which forms a clique of size s + 1 with v, contradicting that ω(D) = s.

Note that using Ramsey's Theorem is the only known way to prove that Forb(K 1,t ) and Forb(S 0, ) are χ-bounded. The resulting bounding functions are very high and certainly very far from being tight. Proposition 11. For the case of out-stars we have,

(i) χ(Forb(T T 3 , S 0,2 )) = 3. (ii) For 3, χ(Forb(T T 3 , S 0, )) 2 -2.
Proof. (i) A digraph in Forb(T T 3 , S 0,2 ) has no vertex of out-degree at least 2. Hence it is the converse of a functional digraph, and its easy to see that the chromatic number is at most 3, so χ(Forb(T T 3 , S 0,2 )) 3.

The directed odd cycles are in Forb(T T 3 , S 0,2 ) and have chromatic number 3. This implies that χ(Forb(T T 3 , S 0,2 )) = 3.

(ii) It suffices to prove that every critical digraph D in Forb(T T 3 , S 0, ) has chromatic number at most 2 -2. Observe that for every vertex v, N + (v) induces a stable set because D is T T 3 -free. The case of S 1,1 -free oriented graphs is also well known, as these are perfect graphs, and therefore χ-bounded. S 1,1 -free orientations of graphs are known as quasi-transitive oriented graphs, and it is a result of Ghouila-Houri ( [START_REF] Ghouila | Houri Caractérisation des graphes non orientes dont on peut orienter les aretes de maniere à obtenir le graphe d'une rélation d'ordre[END_REF]) that a graph has a quasi-transitive orientation if and only if it has a transitive orientation, that is an orientation both acyclic and quasi-transitive (such graphs are commonly called comparability graphs). Note that if a graph has a transitive orientation, then cliques correspond to directed paths; according to a classical theorem, due independently to Gallai [START_REF] Gallai | On directed paths and circuits[END_REF], Hasse [START_REF] Hasse | Zur algebraischen bergründ der graphentheorie I[END_REF], Roy [START_REF] Roy | Nombre chromatique et plus longs chemins d'un graphe[END_REF], and Vitaver [START_REF] Vitaver | Determination of minimal colouring of vertices of a graph by means of boolean powers of the incidence matrix[END_REF], the chromatic number of a digraph is at most the number of vertices of a directed path of maximum length : this implies that comparability graphs are perfect.

Thus d + (v) -1 since D is S 0, -
Oriented graphs in Forb( C 3 , T T 3 , S 1,1 ) and in Forb(T T 3 , S 1,1 ) actually have a very simple structure as we show now.

Theorem 12. Every connected (T T 3 , S 1,1 )-free oriented graph D satisfies the following:

(i) If D is C 3 -free, then D is an extension of T T 2 . (ii) If D contains a C 3 , then D is an extension of C 3 .
Proof. All vertices of an oriented graph D ∈ Forb( C 3 , T T 3 , S 1,1 ) are clearly either a source or a sink, which implies (i).

Now let D ∈ Forb(T T 3 , S 1,1 ). If D does contain no C 3 , then it is an extension of T T 2 (and thus of C 3 ) and we are done. So we may assume that D contains a C 3 . Let (A, B,C) be the partition of a maximal extension of C 3 in D such that none of the sets A, B, C is empty, where all the arcs are from A to B, from B to C and from C to A. If A ∪ B ∪C = V (D) we are done, so we may assume without loss of generality that there exists adjacent vertices a ∈ A and x ∈ D -(A ∪ B ∪C). By directional duality we may assume that a → x. For all c ∈ C, c is adjacent to x for otherwise {c, a, x} induces S 1,1 and x → c for otherwise {a, x, c} induces a T T 3 .

Let c ∈ C. For all a ∈ A, a and x are adjacent for otherwise {x, c, a } induces a S 1,1 , and a → x for otherwise {a , x, c} induces a T T 3 . Moreover x is not adjacent to any vertex b ∈ B, otherwise {a, x, b} induces a T T 3 . Hence D A ∪ B ∪C ∪ {x} is an extension of C 3 with partition (A, B,C ∪ {x}) , contradicting the maximality of (A, B,C).

Corollary 13. χ(Forb( C 3 , T T 3 , S 1,1 )) = 2 and χ(Forb(T T 3 , S 1,1 )) = 3.

Forbidding T T 3 and an oriented star

The triangle-free case for stars is easy. Proposition 14. Let k and be two positive integers.

χ(Forb( C 3 , T T 3 , S k, )) 2k + 2 -2.
Proof. Let D be a (2k + 2 -1)-critical ( C 3 , T T 3 )-free oriented graph. Let V -be the set of vertices of in-degree less than k and let V + be the set of vertices of out-degree less than . By Proposition 7, χ(D V -) 2k -1 and χ(D V + ) 2 -1. Consequently, V -∪ V + = V (D) for otherwise D would be (2k + 2 -2)-colourable. Hence, there is a vertex v with in-degree at least k and out-degree at least . Thus v is the center of an S k, , which is necessarily induced because D is ( C 3 , T T 3 )-free. [START_REF] Kierstead | Applications of hypergraph colouring to colouring graphs that do not induce certain trees[END_REF] proved that the class Forb( C 3 , S k, ) is χ-bounded (without providing any explicit bound). The goal of this section is to prove the following counterpart to that theorem.

Kierstead and Rödl

Theorem 15. For every positive integers k and , the class Forb(T T 3 , S k, ) has bounded chromatic number.

As mentioned in the introduction this can be seen as the next step towards Conjecture 4 because Forb(Or(K 3 ), S k, )) ⊂ Forb(T T 3 , S k, )) ⊂ Forb(Or(K 4 ), S k, )).

As already mentionned, in order to prove Theorem 15 it suffices to prove the following one.

Theorem 16. For every positive integer k, Forb(T T 3 , S k,k ) has bounded chromatic number.

The proof of Theorem 16 is given in the next subsections.

Reducing to triangle-free colouring

Let D be a digraph. A triangle-free colouring is a colouring of the vertices such that no triangle is monochromatic. The triangle-free chromatic number, denoted by χ T (D), of D is the minimum number of colours in a triangle-free colouring of D.

Lemma 17. If D ∈ Forb(T T 3 , S k,k ), then χ(D) (4k -2) • χ T (D) Proof. Let V 1 , . . . ,V χ T (D) be a triangle-free colouring of D. For every i χ T (D), the graph D[V i ] is ( C 3 , T T 3 , S k,k )-free and thus χ(D[V i ]) 4k -2 by Proposition 14. Hence χ(D) (4k -2) • χ T (D).
Lemma 17 implies that in order to Theorem 16 it is sufficient to prove the following theorem.

Theorem 18. For any positive integer k, χ T (Forb(T T 3 , S k,k )) < +∞.

We prove Theorem 18 in Section 3.2.3, and this will establish Theorem 16 as well. The proof requires several preliminaries. To make the proof clear and avoid tedious calculations, we do not make any attempt to get an explicit constant C k such that χ T (Forb(T T 3 , S k,k )) < C k , because our method yields a huge constant which is certainly a lot larger than χ T (Forb(T T 3 , S k,k )).

Preliminaries

A combinatorial lemma. We start with a combinatorial lemma that only serves to prove Lemma 21. Proof. Set |V | = n. We need to prove that if n is sufficiently large, then |E| < k/p k . Let ϕ : V k → N be the function defined as follows: for any k-subset T of V , let ϕ(T

) = |{A ∈ E | T ⊆ A}|. Set Φ = Σ T ∈V k ϕ(T ).
By the hypothesis we have ϕ(T ) k -1 for all T ∈ V k , and thus Φ n k • (k -1). Since each hyperedge contributes to at least pn k to Φ, we have

Φ |E| • pn k . So |E| • pn k (k -1) • n
k , and thus

|E| (k -1) • n k pn k ∼ n→∞ k -1 p k ,
which implies the result.

The constants. All along the proofs we will use several constants; we introduce all of them here.

• k 2 is a fixed integer (that corresponds to the forbidden S k,k ).

• s = 1 -1 2k .

• We choose ε ∈]0, 1 2k [.

• We choose t ∈]s, 1ε[ (we need t > s in Lemma 22 and 23 and we need t < 1ε in Lemma 24).

• g = k/(1tε) k (this corresponds to the constant k/p k in Lemma 19 for p = 1tε).

•

N 1 = max N(k, 1 -t -ε), (1-t-ε)•g ε + g
where N is the function defined in Lemma 19.

• N 2 = max(N 1 , g t-s + g + 1). • there is no arc from B to A,

• d = max N 2 t +
• for every a ∈ A, we have d + B (a) τ|B| and

• for every b ∈ B, we have d - A (b) τ|A|.
If A B and A → τ B, we write A τ B.

The tools. We now prove several lemmas that will be used in the proof.

Lemma 20. Let D ∈ Forb(T T 3 , S k,k ). Let x ∈ V (D). Then N + (x) N -(x).
Proof. Since D is T T 3 -free, N + (x) and N -(x) are stable sets and any arc between N + (x) and N -(x) has its tail in N + (x) and its head in

N -(x). Since D is S k,k -free, D[N -(x), N + (x)] is K k,k -free.
The next lemma roughly states that if A and B are two large enough disjoint stable sets such that A B, then up to deleting a few vertices from A and B we have A t B. Lemma 21. Let A, B be two disjoint stable sets such that A B. If |A|, |B| N 1 , then there exist A 1 ⊆ A and B 1 ⊆ B such that:

• |A 1 | |A| -g, |B 1 | |B| -g and • A 1 t B 1 . Proof. Assume that |A|, |B| N 1 . Let A 2 ={a ∈ A : d + B (a) < (t + ε)|B|} and A 1 = A \ A 2 , and B 2 ={b ∈ B : d - A (b) < (t + ε)|A|} and B 1 = B \ B 2 .
Let us first prove that both |A 2 | and |B 2 | are at most g. Consider the hypergraph

H B = (B, E B ) where E B = {B \ N + (a) | a ∈ A 2 }. We have |E B | = |A 2 | and the size of each hyperedge of H B is at least (1 -t -ε)|B|. Since D[A, B] is K k,k -free, k vertices of A 2 cannot have k common non-neighbours, i.e., the intersection of any k hyperedges of H B is at most (k -1). Since |B| N 1 N(k, 1 -t -ε), Lemma 19 ensures that |A 2 | = |E B | k (1-t-ε) k = g. Thus |A 1 | |A| -g. Similarly |B 2 | g and so |B 1 | |B| -g. Since A B, we have A 1 B 1 .
Thus it remains to prove that A 1 → t B 1 . Since d + B (a) (t + ε)|B| for every a ∈ A 1 , we have:

d + B 1 (a) (t + ε)|B| -|B 2 | t • |B 1 | + ε|B 1 | -(1 -t -ε)|B 2 |) (because |B| = |B 1 | + |B 2 |)
Now |B 2 | g and by definition of N 1 , we have:

|B 1 | |B| -g N 1 -g (1-t-ε)•g ε . So ε|B 1 | (1 -t -ε)|B 2 |. Consequently, d + B 1 (a) t • |B 1 |. Similarly, we obtain d - A 1 (b) t • |A 1 | for all b ∈ B 1 ,
a i ∈ A k , at most (1 -τ)|B| vertices in B are not in N + (a i ). Similarly for each c i ∈ C k , at most (1 -τ)|B| vertices in B are not in N -(c i ). Thus the size of X := 1 i k N + (a i ) ∩ 1 i k N -(c i ) ∩ B is at least (1 -2k(1 -τ))|B| > (1 -2k(1 -s))|B| = 0. Since X is non-empty, it contains a vertex x. The set {x} ∪ A k ∪C k induces S k,k , a contradiction.
All along this section, we apply this lemma with stronger assumptions.

Corollary 23. Let D ∈ Forb(T T 3 , S k,k ) and τ ∈]s, 1[. Let A, B,C be three disjoint stable sets of D. If A → τ B → τ C, then C A.
The next lemma roughly ensures that if A, B,C are three large enough stable sets such that A B C, then, up to deleting a few vertices from A and C, we have C A.

d + B 3 (a) t|B 1 | -g t - g |B 1 | |B 3 | and d - B 3 (c) t|B 2 | -g t - g |B 2 | |B 3 | By Lemma 22, it is sufficient to prove that t -g/|B i | > s for i = 1, 2, which is satisfied because |B i | |B| -g N 2 -g > g t-s . A digraph D is c-triangle-free-critical if χ T (D) = c and for all x ∈ V (D), χ T (D -{x})) < c. Lemma 25. Let D ∈ Forb(T T 3 ) be a c-triangle-free-critical digraph. Then for all x ∈ V (D), d + (x) c -1 and d -(x) c -1. Proof. Let x ∈ V (D).
Let π be a triangle-free colouring of Dx using c -1 colours. Since χ T (D) = c, we cannot extend π to D using a colour in {1, . . . , c -1}. Let i c -1. Since x cannot be coloured with i, the vertex x is adjacent to two vertices u i and v i coloured i and such that (u i , v i ) is an arc. Since D is T T 3 -free, necessarily, v i → x and x → u i . Now all the u i (resp. v i ) are distinct because they are coloured with distinct colours, so d + (x) c -1 and d -(x) c -1.

Proof of Theorem 18

We are now able to prove Theorem 18. In fact, we prove the following theorem.

Theorem 26. χ T (Forb(T T 3 , S k,k )) 2d.

Proof. We consider a minimal counter-example, that is, a digraph D ∈ Forb(T T 3 , S k,k ) which is (2d + 1)-triangle-free-critical. By Lemma 25, every vertex of D has in-and out-degree at least 2d.

Let A, B be two disjoint stable sets, each of size at least N 2 t , such that A t B and maximizing |A| + |B|. We have:

|A| + |B| 4d -2g. (1)
Such sets exist. Indeed let x be a vertex. By Lemma 20, we have N + (x) N -(x). Since 2d N 1 , Lemma 21 ensures that there exists a U ⊆ N -(x) and V ⊆ N + (x) both of size at least 2dg such that U t V . Moreover both U and V are stable sets since D is T T 3 -free. So U and V satisfies the conditions. t , we also have

|B int a | N 2 .
Since

d + C 1 (b) t • |C 3 | t • (|C 1 | -2g) = t - 2tg |C 1 | • |C 1 |. (2)
d + C 1 (b) t • |C 4 | t • (|C 1 | -g) = t - tg |C 1 | • |C 1 |. (3)
Since

C 1 A 1 and |C 1 |, |A 1 | N 2 , Lemma 21 ensures the existence of A 3 ⊆ A 1 and C 5 ⊆ C 1 such that |A 3 | |A 1 | -g, |C 5 | |C 1 | -g and C 5 t A 3 .
So, for all a ∈ A 3 , we have:

d - C 1 (a) t • |C 5 | t • (|C 1 -g) t - tg |C 1 | • |C 1 |. ( 4
) Set p = (t -tg |C 1 |
). Then (2), ( 3) and ( 4)

ensures that for all b ∈ B 2 ∪ B 2 a , d + C 1 (b) p|C 1 | and for all a ∈ A 3 , d - C 1 (a) p|C 1 |. Moreover, since |C 1 | > d -g 2tg (t-
| -g = |A 1 | -2g = |A| -3g N 2 t . and |B 2 | = |B | -2g. Moreover |B * | |B 2 | -g |B 1 | -2g |B | -3g d -8g by Claim 26.2. Since d N 2 t + 8g, we have |B * | N 2
t . Furthermore the following inequalities are satisfied:

|A * | + |B * | |A 3 | + |B 2 | + |B 2 a | -2g |A| + |B int a | + |B ext a | + |B | -7g |A| + |B| + |B ext a | -7g > |A| + |B|.
The first inequality is due to the last extraction. The second comes from Kierstead and Trotter [START_REF] Kierstead | Colorfull induced subgraphs[END_REF] proved that Forb(P + (3)) is not χ-bounded. In fact, they show that an analogue of Zykov's construction of triangle-free graphs with arbitrarily large chromatic number yields acyclic (T T 3 , P + (3))-free oriented graphs with arbitrary large chromatic number. Interestingly, a result of Galeana-Sánchez et al. [START_REF] Galeana-Sánchez | On the structure of strong 3-quasitransitive digraphs[END_REF] implies that χ(Forb( C 3 , T T 3 , P + (3))∩S ) = 2. Galeana-Sánchez et al. [START_REF] Galeana-Sánchez | On the structure of strong 3-quasitransitive digraphs[END_REF] studied 3-quasi-transitive digraphs, which are digraphs in which for every directed walk (u, v, w, z) either u and z are adjacent or u = z. In particular, every ( C 3 , T T 3 , P + (3))-free oriented graph is 3-quasi-transitive. They characterized the strong 3quasi-transitive digraphs. They showed that every such graph is either semicomplete, or semicomplete bipartite, or in the set F of oriented graphs D that have three vertices

|A 3 | |A 1 | -g |A| -2g and |B 2 a | |B a | -g = |B int a | + |B ext a | -
{v 1 , v 2 , v 3 } such that A(D) = {v 1 v 2 , v 2 v 3 , v 3 v 1 } ∪ u∈V (D)\{v 1 ,v 2 ,v 3 } {v 1 u, uv 2 }.
Recall that a digraph D is semicomplete if for any two vertices u, v ∈ V (D) at least one of the two arcs uv and vu is in A(D), and that it is semicomplete bipartite if there is a bipartition (A, B) of V (D) such that if for any a ∈ A and b ∈ B, at least one of the two arcs ab and ba is in A(D). Since semicomplete digraphs and members of F are not ( C 3 , T T 3 )-free, strong ( C 3 , T T 3 , P + (3))-free oriented graphs are bipartite tournaments and consequently have chromatic number at most 2. On the other hand, Forb(P + (3)) ∩ S is not χ-bounded. Indeed, adding to every acyclic (T T 3 , P + (3))-free oriented graph D a vertex x which dominates all sources of D and is dominated by all other vertices, we obtain a strong (Or(K 4 ), P + (3))-free oriented graph D with chromatic number χ(D) + 1; since χ(Forb( C , T T 3 , P + (3))) = +∞, we get χ(Forb(Or(K 4 ),

P + (3)) ∩ S) = +∞.
The shift graph Sh k (n), introduced by Erdős and Hajnal [START_REF] Erdős | On the chromatic number of infinite graphs[END_REF], is the graph whose vertices are the k-element subsets of {1, . . . , n} and two vertices a = {a 1 , . . . ,

a k } and b = {b 1 , . . . , b k } are adjacent iff a 1 < a 2 = b 2 < a 3 = b 3 < • • • < a k-1 = b k-1 < b k .
Gyárfás pointed out that the natural orientations of shift graphs are in Forb( C 3 , T T 3 , P + (1, 1, 1)) but may have arbitrarily large chromatic number. Consequently, Forb(P + (1, 1, 1)) is not χ-bounded. Another way of seeing this is to note that every line oriented graph (i.e. an oriented graph which is a line digraph) is both T T 3 -free and P + (1, 1, 1)-free and that the line oriented graph of an acyclic oriented graph is also acyclic. Now, since it is well known that the chromatic number of the line digraph of D is at least log(χ(D)), this implies that the line oriented graphs of T T n form a family of oriented graphs in Forb( C 3 , T T 3 , P + (1, 1, 1)) with arbitrarily large chromatic number (which is consistent with Gyárfás's remark since natural orientations of shift graphs are in fact line oriented graphs). It can be deduced from Corollary 4.5.2 in [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] that in fact the class of line oriented graphs is exactly Forb(T T 3 , P + (1, 1, 1),C(3, 1),C(2, 2)), where

C(3, 1) (resp. C(2, 2)) is the oriented cycle (a 1 , a 2 , a 3 , a 4 , a 1 ) such that a 1 → a 2 → a 3 → a 4 ← a 1 (resp. a 1 → a 2 → a 3 ← a 4 ← a 1 ).
It follows that Forb( C , T T 3 , P + (1, 1, 1),C(3, 1),C(2, 2)) has unbounded chromatic number.

Forbidding

P + (2, 1) Theorem 27. χ(Forb( C 3 , T T 3 , P + (2, 1)) = 3.
This result will be a consequence of the following lemma.

Lemma 28. Let D be a ( C 3 , T T 3 , P + (2, 1))-free oriented graph. Then the following holds (1) Every oriented odd hole in D is directed.

(2) If a strong component of D contains an odd hole, then it is an initial strong component.

(3) If D is strongly connected, then there is a stable set S that intersects every odd hole of D.

We first observe that this lemma implies Theorem 27.

(3) Suppose that D is strongly connected. If D contains no oriented odd hole, then the result holds with S = / 0. If D contains an odd hole C = (v 1 , . . . , v q , v 1 ), then it is directed by [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF] and by Claim 28.1, every vertex of D is the C-twin of some v i . For 1 i q, let T i be the set C-twins of v i plus v i . Observe that if xy ∈ A(D) with x ∈ T i and y ∈ T j , then |i -j| = 1 mod q, for otherwise (v i-1 , x, y, v j-1 ) would be an induced P + (2, 1). It follows that D -T 1 has no odd cycles, and T 1 is a stable set because all vertices in T 1 are in N -(v 2 ). Thus T 1 is our desired S.

Remark 29. Wang and Wang [START_REF] Wang | The structure of strong arc-locally in-semicomplete digraphs[END_REF] study a class of digraphs that contains Forb( C 3 , T T 3 , P + (2, 1)). A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x, y, every inneighbour of x and every in-neighbour of y are either adjacent or the same vertex. Observe that the oriented graphs of Forb( C 3 , T T 3 , P + (2, 1)) are in-semicomplete. In particular, [START_REF] Wang | The structure of strong arc-locally in-semicomplete digraphs[END_REF] characterizes strong arc-locally in-semicomplete digraphs. This characterization implies that every strong oriented graph in Forb(P + (2, 1)) is either a bipartite tournament (i.e. the orientation of a complete bipartite graph) or an extension of a directed cycle. This directly implies Lemma 28 (3).

Forbidding T T 3 and P + (2, 1).

We shall now prove that χ(Forb(T T 3 , P + (2, 1))) = 4. Here is a short sketch of the proof. We first describe precisely the structure of a strong (T T 3 , P + (2, 1))-free oriented graph that contains an odd hole (see Lemma 30). This permits us to colour such oriented graphs, more precisely we distinguish between two cases, if the oriented graph contains an odd hole of length 7 or more, then it is 3-colourable; if it contains an odd hole of length 5, then it is 4-colourable. We also give a tight example in the second case (see Lemmas 31 and 32). Finally we show how to 4-colour any (T T 3 , P + (2, 1))-free oriented graph (Theorem 33).

Lemma 30. Let D be a digraph in Forb(T T 3 , P + (2, 1)), and let H = (v 1 , . . . , v 2k+1 , v 1 ), k 2, be an odd hole in D. Then:

(i) H is directed. (ii) If u ∈ Reach -(H) \V (H), then u is adjacent to some vertex of H.
(iii) If v dominates a vertex in V (H), then either there is an index i such that vv i , v i-2 v are the only two arcs between v and V (H) or k = 2 and there are exactly three arcs between V (H) and v and these are either vv i , v i-2 v, vv i+2 or vv i , v i-2 v, v i+1 v for some i ∈ {1, . . . , 5}.

(iv) If N + (v) ∩V (H) = / 0 but N -(v) ∩V (H) = / 0, then |N -(v) ∩V (H)| = 1.
(v) H is contained in an initial strong component of D.

Proof. In all this proof, indices of the v i are modulo 2k + 1.

(i) Every oriented odd hole contains a directed path of size at least 2. Thus, unless it is directed, it contains a P + (2, 1).

(ii) Let u be a vertex in Reach -(H) \V (H) outside H. Let P = (x 0 , x 1 . . . , x q ) be a shortest (u,V (H))-dipath. (Hence u = x 0 ). If q = 1 there is nothing to prove, so assume q 2. We may assume, by relabelling V (H) if necessary, that x q = v 2k+1 . As D is T T 3 -free, the vertices x q-1 and v 2k are not adjacent. Consequently, as D is P + (2, 1)-free, x q-2 must be adjacent to either v 2k+1 or to v 2k . By the minimality of P the arc will enter x q-2 in both cases. Thus, since D is T T 3 -free, D contains exactly one of those arcs. If q = 2, we are done since u is adjacent to a vertex of H so suppose q 3. If v 2k → x q-2 (resp. v 2k+1 → x q-2 ), then since D is (T T 3 , P + (2, 1))-free, the vertices v 2k-1 (resp. v 2k ) and x q-3 are adjacent, so, by minimality of P, v 2k-1 → x q-3 (resp. v 2k → x q-3 ). And so on by induction, one proves that there is an arc from H to x q-4 , x q-5 , etc until we get an arc from H to u. This proves (ii).

(iii) Let v be a vertex in V (D) \ V (H) that dominates a vertex, say v i , in H. Moreover, without loss of generality, we may assume that vv i-2 is not an arc. Indeed if v dominates v i-2 for all i, then v would dominate all vertices of H and D would contain a T T 3 .

Since D is T T 3 -free, then v and v i-1 are not adjacent. Now there can be no arc v j v with j ∈ {i -2, i, i + 1} for otherwise (v j , v, v i , v i-1 ) would be an induced P + (2, 1). Furthermore, since D has no induced P + (2, 1), there is an arc between v and v i-2 . By our assumption, this arc is v i-2 v i . Now, there can be no arc vv j with j ∈ {i -3, i} for otherwise (v i-2 , v, v j , v j-1 ) would be an induced P + (2, 1) or D {v, v j-1 , v j } would be a T T 3 . Consequently, in addition to vv i and v i-2 v i , the only possible arcs between v and H are v i+1 v and vv i-3 . If k 3, then

vv i-3 / ∈ A(D) for otherwise (v i-5 , v i-4 , v i-3 , v) is an induced P + (2, 1), and v i+1 v / ∈ A(D), for otherwise (v i-3 , v i-2 , v, v i+1 ) is an induced P + (2, 1). If k = 2, then i -3 = i + 2.
Both v i+1 v and vv i+2 , cannot be arcs for otherwise {v, v i+1 , v i+2 } induces a T T 3 . This completes the proof of (iii).

(iv) Assume for a contradiction that N + (v) ∩V (H) = / 0 and |N -(v) ∩V (H)| 2. There are distinct induces i and j such that v i v and v j v are arcs. Observe that i / ∈ { j -1, j + 1} because D has no T T 3 , and v j-1 and v are not adjacent because N + (v) ∩ V (H) = / 0 and D has no T T 3 . If | j -2| = 2 then (v j-1 , v j , v, v i ) is an induced P + (2, 1) and if i = j -2, then (v i-1 , v i , v, v j ) is an induced P + (2, 1), so we obtain the desired contradiction.

(v) Suppose for a contradiction that H is contained in a strong component C that is not initial. Then there is a vertex u ∈ Reach -(H) \ V (C) such that u belongs to an initial component. By (ii), u is adjacent to a vertex in H. If u dominates a vertex in H, then by (iii) it is also dominated by a vertex of H. Hence in any case, u is dominated by a vertex of H. But this implies that u ∈ C, a contradiction. Lemma 31. Let D be a strong digraph in Forb(T T 3 , P + (2, 1)). If D contains an odd hole H with at least 7 vertices, then D is an extension of H. In particular χ(D) = 3.

Proof. Let H = (v 1 , . . . , v 2k+1 , v 1 ), k 3 be an odd hole in D. By Lemma 30 (i)-(ii), H is directed and every vertex of V (D) \ V (H) is adjacent to V (H). Suppose D is not an extension of H. Then by Lemma 30 (iii)-(iv) there is a vertex x 1 such that N + (x 1 ) ∩ V (H) = / 0 and |N -(x 1 ) ∩ V (H)| = 1. Let v j be the vertex of N -(x 1 ) ∩ V (H). As D is strong there exists a (x 1 , H)-dipath. Let P = (x 1 , x 2 , . . . , x t , v i ) be a shortest such dipath. Then by minimality of P, x t is the only vertex of P-{v i } that has an arc to V (H). By Lemma 30 (iii), v i-2 x t , x t v i are the only arcs between x t and V (H). Now, x t-1 must be adjacent to v i-3 , otherwise (v i-3 , v i-2 , x t , x t-1 ) is an induced P + (2, 1). As x t-1 has no arc to V (H) we have that v i-3 x t-1 is an arc and by We now describe a (T T 3 , P + (2, 1))-free oriented graph with chromatic number 4. Take two 5-holes C 1 = (v 1 , v 2 , v 3 , v 4 , v 5 , v 1 ) and C 2 = (u 1 , u 2 , u 3 , u 4 , u 5 , u 1 ) and for each vertex u i we add the arcs v i-1 u i , u i v i+1 and u i v i+3 (see figure 4). It is a routine exercise to check that this oriented graph is indeed (T T 3 , P + (2, 1))-free. In any 3-colouring of C 1 , there exists i ∈ {1, . . . , 5} such that the vertices v i-1 , v i+1 , v i+3 have distinct colours, and thus no colour is available for u i . So this graph is not 3-colourable.

v 1 v 2 v 3 v 4 v 5
Theorem 33. χ(Forb(T T 3 , P + (2, 1))) = 4. More precisely, if D is a (T T 3 , P + (2, 1))-free oriented graph, then the following hold.

• χ(D) 4;

• If D contains an odd hole of length 7 or more, then χ(D) = 3.

Proof. Let D ∈ Forb(T T 3 , P + (2, 1)) and assume D is connected. We may assume that D admits at least one initial strong component K that contains an odd hole, otherwise by Lemma 30 (v) D is odd hole-free and thus is 4-colourable by Theorem 3.

Claim 33.1. K is the only initial strong component of D.

Proof. Assume D contains another initial strong component K . Let P = (p 1 , p 2 , . . . , p k ) be a shortest path from K to K , where p 1 ∈ K and p k ∈ K . Note that since K and K are initial strong components p 1 → p 2 and p k → p k-1 . As K is strong and non-trivial there exists a vertex p 0 in V (K) \ {p 1 } such that p 0 → p 1 . Observe that by minimality of P, and since D is T T 3free, P = (p 0 , p 1 , . . . , p k ) is an induced path. Moreover, since p 0 → p 1 → p 2 and p k-1 ← p k , necessarily P contains a P + (2, 1), a contradiction. ♦

Let dist(K, x) denote the distance from K to x, that is the length of a shortest dipath from K to x in D. Note that dist(K, x) is well-defined for every vertex x ∈ V (D), because K is the only initial strong component, so every vertex can be reached from K. Set L i = {x : dist(K, x) = i} (in particular L 0 = K). Clearly, the L i partition V (D). If j > i, an arc from L j to L i is called a backward arc.

Claim 33.2. D has no backward arcs.

Proof. Assume for contradiction that uv is a backward arc from L j to L i and assume it has been chosen with respect to the minimality of i. Observe that i 1. If i 2, then there exists a vertex

v 1 ∈ L i-1 and a vertex v 2 ∈ L i-2 such that v 2 → v 1 → v and thus (v 2 , v 1 , v, u) is a P + (2, 1
) and it is induced by minimality of i, a contradiction. So we may assume that i

= 1. Let v 1 ∈ L 0 such that v 1 → v. There exists a vertex v 2 ∈ L 0 such that v 2 → v 1 and since D is T T 3 -free, v 2 is not adjacent to v. Hence {v 2 , v 1 , v, u} induces a P + (2, 1), a contradiction. ♦ Claim 33.3. For any i 2, L i is a stable set.
Proof. Let i 2 and assume that uv is an arc of L i . There exists

v 1 ∈ L i-1 and v 2 ∈ L i-2 such that v 2 → v 1 → v. So (v 2 , v 1 , v, u) is a P + (2, 1
) and it is induced since there is no T T 3 nor backward arcs. ♦

A directed bipartite graph is an orientation of a connected bipartite graph such that every vertex is either a source or a sink.

Claim 33.4. L 1 is a disjoint union of directed bipartite graphs.

Proof. Assume for contradiction that there exists a, b, c ∈ L 1 such that a → b → c (note that ca might or might not be an arc). We distinguish between two cases. Case 2: no neighbour of c in L 0 belongs to an odd hole in L 0 . Let c 1 ∈ L 0 be a neighbour of c. By Lemma 31, if L 0 contains an odd hole of length at least 7, then all vertices of L 0 belong to an odd hole. So we may assume that L 0 contains a 5-hole, say H = (u 1 , u 2 , u 3 , u 4 , u 5 , u 1 ). By property 30 (iii), we may assume without loss of generality that u 2 → c 1 → u 4 and that exactly one of u 5 c 1 , c 1 u 1 is an arc. Recall again that by Lemma 30 (iv), a vertex in L 1 is adjacent to at most one vertex in H.

Since (u 2 , c 1 , c, b) cannot be induced, u 2 b is an arc. Since (u 1 , u 2 , b, a) cannot be induced, u 1 a is an arc. Since (a, b, c, c 1 ) cannot be induced and c 1 a is not an arc by Lemma 30 (iv), c and a are adjacent and we have c → a. But now (u 5 , u 1 , a, c) is an induced P + (2, 1) (it is indeed induced because c has no neighbour in H), a contradiction. ♦

We may now assume that L 1 consists of t directed bipartite graphs (A 1 , B 1 ), . . . , (A t , B t ) such that all arcs of L 1 are from A i to B i .

Claim 33.5. Let 1 i t and let u, v ∈ A i . Then u and v have the same neighbourhood in L 0 and the graph induced by N L 0 (B i ) and N L 0 (A i ) is a complete bipartite graph.

Proof. Assume for a contradiction that there exists a vertex u ∈ L 0 such that u u is an arc but u v is not. As (A i , B i ) is connected, we may assume without loss of generality that u and v have a common neighbour in B i , say w. Then (u , u, w, v) induces a P + (2, 1), a contradiction.

Let w ∈ B i and w be a neighbour of w in L 0 . Let u ∈ A i be a neighbour of w. Let u ∈ N L 0 (A i ). Since u dominates all vertices of A i , u dominates u and thus u = w, otherwise (u , u, w) is a T T 3 , and u is adjacent to w , otherwise (u , u, w, w ) induce a P + (2, 1). ♦ Claim 33.6. Let i 2 and let u ∈ L i . Then the neighbours of u in L i-1 have the same neighbourhood in L i-2 .

Proof. Let v, w be two neighbours of u in L i-1 . Since there is no backward arcs, vu and wu are arcs. If some z ∈ L i-2 was adjacent to precisely one of v, w, say v, then (z, v, u, w) would induce a P + (2, 1). Hence v and w share the same in-neighbourhood, which implies the claim. ♦

We are now going to explain how a k-colouring of L 0 (where k = 3 or 4), can be extended to the rest of the graph. So assume that L 0 is coloured with colours from {1, 2, . . . , k}.

We start by colouring L 1 . Let 1 i t and let I ⊆ {1, . . . , k} be the set of colours used to colour N L 0 (A i ). Since N L 0 (B i ) is complete to N L 0 (A i ), I = {1, . . . , k} and only colours from {1, . . . , k} -I are used to colour N L 0 (B). So we can colour the vertices of A i with a colour from {1, . . . , k} -I and the vertices in B i with a colour from I. Hence we can colour all vertices of L 1 . Moreover assume we are doing so in such a way that two vertices of L 1 that are sharing the same neighbourhood in L 0 are coloured with the same colour. Now we colour the rest of the graph layer by layer. Assume that all layer below L i (i 2) have already been coloured in such a way that two vertices in the same layer that have the same neighbour in the layer below are coloured with the same colour. Then, by Claim 33.6, each vertex in L i see a single colour in L i-1 , so it is easy to extend the colouring.

Forbidding several orientations of P 4

Observe that, by directional duality, Forb(P + (3), P + (2, 1)) = Forb(P + (3), P -(2, 1)).

Proposition 34. An oriented graph in Forb(P + (3), P + (2, 1)) or Forb(P + (3), P + (1, 1, 1)) contains no odd hole.

Proof. Let D be a (P + (3), P + (2, 1))-free oriented graph. Assume for a contradiction, that it contains an odd hole C = (v 1 , . . . , v p , v 1 ). Necessarily, C contains two consecutive edges that are oriented in the same direction. Without loss of generality, v 1 → v 2 → v 3 . Now (v 1 , v 2 , v 3 , v 4 ) is either a P + (3) or a P + (2, 1), a contradiction.

Let D be a (P + (3), P + (1, 1, 1))-free oriented graph. Assume for a contradiction, that it contains an odd hole C = (v 1 , . . . , v p , v 1 ). Necessarily, C contains two edges at distance 1 that are oriented in the same direction. Without loss of generality, v 1 → v 2 and v 3 → v 4 . Now (v 1 , v 2 , v 3 , v 4 ) is either a P + (3) or a P + (1, 1, 1), a contradiction. A recent and difficult paper of Seymour and Scott (see [START_REF] Scott | Colouring graphs with no odd holes[END_REF]) proves that the class of oddhole-free graphs is χ-bounded, which directly yields the following results.

Corollary 35. Forb(P + (3), P + (2, 1)), Forb(P + (3), P -(2, 1)), and Forb(P + (3), P + (1, 1, 1)) are χ-bounded.

A natural question is to ask for the values (or nice bounds) of χ(Forb(Or(K k ), P + (3), P + (2, 1))) and χ(Forb(Or(K k ), P + (3), P + (1, 1, 1))) for every k 3. A graph with no odd hole nor clique of size 3 contains no odd cycle and thus is bipartite. Thus Proposition 36. χ(Forb( C 3 , T T 3 , P + (3), P + (2, 1))) = χ(Forb( C 3 , T T 3 , P + (3), P + (1, 1, 1))) = 2.

One can also easily prove the following proposition. This proposition also derives directly from Theorem 27 and the fact that directed odd cycles are in Forb( C 3 , T T 3 , P + (2, 1), P + (1, 1, 1)).

Concluding Remarks

Let us conclude by discussing the remaining open cases. Conjecture 4 about stars is still widely open, the next case to study being Forb(Or(K 4 ), S k,k ). About oriented paths, note that since Forb(P + (3)) and Forb(P + (1, 1, 1)) are not χ-bounded, the only open cases for orientations of P k that would be χ-bounding are paths of the type P + (2, 2, . . . , 2) or P + (1, 2, 2, . . . , 2), or P + (1, 2, 2, . . . , 2, 1) (following our notations). In fact for trees in general, most orientations will contain either P + (3) and P + (1, 1, 1) and hence when forbidden will define classes that are not χ-bounded.

Recall that Conjecture 1 states that for every tree T , the class of T -free graphs is χ-bounded. A stronger conjecture could be the following : for every tree T , there exists one orientation T of T such that the class of graphs that admit a T -free orientation is χ-bounded. This is false for many trees, as shown below.

Proposition 38. There exists a tree T such that for every orientation T of T , Forb( T ) is not χ-bounded.

Proof. To construct T , start with an induced path on four vertices {v 1 , v 2 , v 3 , v 4 } and add vertices {w 1 , w 2 , w 3 , w 4 } such that N(w i ) = {v i }. It is easy to see that every orientation of this tree contains either a P + (3) or P + (1, 1, 1). Therefore Forb( T ) contains either Forb(P + (3)) or Forb(P + (1, 1, 1)) which are both not χ-bounded.

Of course any tree that contains this tree T will also satisfy the theorem. Up to our knowledge, Gyárfás-Summner conjecture (Conjecture 1) is not known to be true for these trees, so they could be natural candidates for counterexamples.

Figure 1 :

 1 Figure 1: The four orientations of P 4

  free. Hence |A(D)| ( -1)|V (D)|. If D contains a vertex of degree less than 2 -2, then by Proposition 7, χ(D) 2 -2. If not, then every vertex has degree exactly 2 -2. Moreover, D is not a tournament of order 2 -1, because every such tournament contains a T T 3 . Hence by Brooks' Theorem (Theorem 8), χ(D) 2 -2.

Lemma 19 .

 19 Let k ∈ N and p ∈ ]0, 1[. Then there is an integer N(k, p) that satisfies the following: If H = (V, E) is a hypergraph where all hyperedges have size at least p|V |, and the intersection of any k hyperedges has size at most k -1, and |V | N(k, p), then |E| < k/p k .

  which completes the proof. Lemma 22. Let τ ∈]s, 1[ and D ∈ Forb(T T 3 , S k,k ). Let A, B,C be three disjoint stable sets of D. If for every a ∈ A, d + B (a) τ|B| and for every c ∈ C, d - B (c) τ|B|, then C A. Proof. Let us first prove that there is no arc from A to C. Let a ∈ A and c ∈ C. Since s > 1 2 , we have d + B (a) τ|B| > 1 2 |B| and d - B (c) τ|B| > 1 2 |B|. So there exists b ∈ B such that b ∈ N + (a) ∩ N -(c), hence ac is not an arc otherwise {a, b, c} would induce a T T 3 , a contradiction. It remains to prove that D[C, A] is K k,k -free. Assume for contradiction that there exist A k = {a 1 , . . . , a k } ⊆ A and C k = {c 1 , . . . , c k } ⊆ C such that there is no arc between A k and C k . For each

Lemma 24 .

 24 Let D ∈ Forb(T T 3 , S k,k ) and let A, B,C be three disjoint stable sets of D. If A B C and |A|, |B|, |C| N 2 , then there exist A 1 ⊆ A, and C 1 ⊆ C such that: • |A 1 | |A|g, |C 1 | |C|g and • C 1 A 1 Proof. The proof consists in combining Lemmas 21 and 22. Since A B and |A|, |B| N 1 , Lemma 21 ensures that there exist A 1 ⊆ A and B 1 ⊆ B such that |A 1 | |A|g, |B 1 | |B|g and A 1 t B 1 . Similarly, since B C and |B|, |C| > N 1 , there exist B 2 ⊆ B and C 1 ⊆ C such that |B 2 | |B|g, |C 1 | |C|g and B 2 t C 1 . Set B 3 = B 1 ∩ B 2 and observe that |B 3 | |B| -2g. Note moreover that both B 1 \ B 3 and B 2 \ B 3 have size at most g. For all a ∈ A 1 , since A 1 → t B 1 and B 2 → t C 1 , we have:

Claim 26 . 1 .Figure 2 :

 2612 Figure 2: The situation in Case 1.

Case 2 :Case 3 :

 23 |B| N 2 t + 4g, and there exists b ∈ B such that d + D-(A∪B) (b) d and d - D-(A∪B) (b) d. This case is analogous to Case 1 by directional duality. The remaining case. Claim 26.1 ensures that there is a vertex x in A∪B with in-and out-degree at least d. Assume that x ∈ A. Since |A| < N 2 t + 4g by Case 1 and |A| + |B| 4d -2g by Equation (1), we have |B| N 2 t + 4g. So Case 2 ensures that no vertex b of B has in and out-degree at least d in the complement of A ∪ B. Let b ∈ B. Thus b has in-degree at most d + N 2 t + 4g -1 (b can be incident to the vertices of A plus less than d vertices in V \ (A ∪ B)) or b has out-degree at most d (there is no arc from B to A). But d + N 2 t + 4g -1 2d -1, which contradicts Lemma 25. The case where x ∈ B is obtained similarly by switching Cases 1 and 2 in the proof. 4 Forbidding Oriented Paths 4.1 Forbidding P + (3) or P + (1, 1, 1)

Figure 3 : 3 Figure 4 :

 334 Figure 3: The colouring π of D -C 2

Case 1 :

 1 c admits a neighbour c 1 ∈ L 0 such that c 1 belong to an odd hole H = (c 1 , . . . , c 2k+1 , c 1 ) of L 0 . Since (c 2k+1 , c 1 , c, b) cannot be induced, c 2k+1 → b and since (c 2k , c 2k+1 , b, a) cannot be induced, c 2k → a. Recall that by Lemma 30 (iv), a vertex in L 1 is adjacent to at most one vertex in H. Since (a, b, c, c 1 ) cannot be induced, we must have c → a. But now (c 1 , c, a, c 2k ) is an induced P + (2, 1), a contradiction.

  Proposition 37.χ(Forb( C 3 , T T 3 , P + (2, 1), P + (1, 1, 1))) = 3.

  and so on . . .

	Let us denote by Or(G) the set of all possible orientations of a graph G, and by Or(G) the
	set of all possible orientations of a graph in the class G. By definition a class of oriented graphs
	D is χ-bounded if and only if for every positive integer n, D ∩ Forb(Or(K n )) has bounded
	chromatic number. The Gyárfás-Sumner conjecture (Conjecture 2) can be restated as follows :
	Forb(Or(H)) is χ-bounded if and only if H is a forest. However Forb(F ) could be χ-bounded

  All of A, B int a and C have size at least N 2 , so, by Lemma 24, there exist A 1 ⊆ A and C 1 ⊆ C such that |A 1 | |A|g, |C 1 | |C|g and C 1 A 1 . By Lemma 20, B a C 1 . Hence we have B a C 1 A 1 and |B a |, |C 1 |, |A 1 | N 2 + g. Applying first Lemma 24 and then Lemma 21, we obtain the existence of A 2 ⊆ A 1 and B 1 a ⊆ B a of respective size at least |A 1 | -2g and |B a | -2g such that A 2 t B 1 We shall now prove the existence of A * ⊆ A and B * ⊆ B ∪B int a ∪B ext a each of size at least N 2 /t such that A * t B The proof is organized as follows: first using Lemmas 20, 21 (several times), 22 and 24, we show that almost all vertices of B have many out-neighbours in C. Then we show the same for almost all vertices in B a . Using this degree assumption and Lemma 21, we establish the existence of large sets A 3 ⊆ A and B 3 ⊆ B ∪ B a such that A 3B 3 . This main fact, combined with few other calculations lead to the existence of the above-mentioned sets A So Lemma 24 ensures that there existC 2 ⊆ C 1 and B 1 ⊆ B such that |C 2 | |C 1 |g, |B 1 | |B |g and B 1 C 2 . Now, since B 1 C 2 and |B 1 |, |C 2 | N 2 ,by Lemma 21, there exist B 2 ⊆ B 1 and C 3 ⊆ C 2 such that |B 2 | |B 1 |g and |C 3 | |C 2 |g such that B 2 t C 3 . So, for all b ∈ B 2 , we have:

	Proof. a . Now, we have A 2 t B 1 a , |A 2 | |A| -3g N 2 t and |B 1 a | |B a | -2g 2d -2g > N 2 t . The
	maximality of |A| + |B| ensures:
	|A| + |B|	|A 2 | + |B 1 a |
	|A| + |B int a | + |B |	|A| -3g + |B int a | + |B ext a | -2g
	|B | |B ext a | -5g	d -5g
			♦
	A B, we have A B int a . Moreover, B int a ⊆ N + (a) and C ⊆ N -(a), so B int a Lemma 20. Hence, A B int a C. Claim 26.2.	C by
	|B | |B ext a | -5g d -5g N 2 + g.

* and |A * | + |B * | > |A| + |B|, which contradicts the maximality of |A| + |B|. * and B * . Since A 1 B and B ⊆ B, we have A 1 B . Thus C 1 A 1 B and |C 1 |, |A 1 |, |B | N 2 + g.

  s) and since t > s, we have p > s. Thus Lemma 22 yields A 3 B 2 ∪ B 2 a . Let us apply Lemma 21 one last time. Indeed, both A 3 and B 2 ∪ B 2 a have size at least N 1 . Thus, there exist A * ⊆ A 3 and B * ⊆ B 2 ∪ B 2 a of size respectively at least |A 3 |g and |B 2 ∪ B 2 a |g such that A * t B * . Observe that |A * | |A 3

  g and |B 2 | |B | -2g. Finally the last inequality comes from the fact that B ext has size at least d which is greater than 7g by definition.

	Thus A *	t B

* , |A * | + |B * | > |A| + |B| and both A * and B * have size at least N 2 t , a contradiction to the maximality of A t B.

Acknowledgement

The authors would like to thank Stéphan Thomassé for stimulating discussions.

* This work was supported by ANR under contract STINT ANR-13-BS02-0007. † Project Coati, I3S (CNRS, UNSA) and INRIA, Sophia Antipolis, France. Part of this work was done while this author was visiting project COATI, Sophia Antipolis. Hospitality and financial support from Labex UCN@Sophia, Sophia Antipolis is gratefully acknowledged. The research of Bang-Jensen was also supported by the Danish research council under grant number 1323-00178B. This author was partially supported by Núcleo Milenio Información y Redes ICM/FIC RC130003 and Basal program

Proof of Theorem 27 assuming Lemma 28. Let D 1 , . . . , D p be the initial strong components of D. By (3), for every 1 k p, there exists a stable set S k ⊆ V (D k ) such that D k -S k has no odd holes. Now S = S 1 ∪ • • • ∪ S p is also a stable set because there is no arc between two initial strong components, and by ( 1) and ( 2), S is a stable set that intersects every odd hole of D. Since D is ( C 3 , T T 3 )-free, this implies that D \ S is bipartite, which concludes the proof.

It remains to prove Lemma 28.

Proof of Lemma 28. To prove (1) it suffices to observe that every oriented odd hole contains a directed path of size at least 2. Thus unless it is directed it contains a P + (2, 1).

Let us prove a claim that will imply (2) and [START_REF] Brooks | On colouring the nodes of a network[END_REF]

Claim 28.1. Let C = (v 1 , . . . , v q , v 1 ) be a directed odd cycle in D, and let x be a vertex in V (D) \V (C). Then:

Proof. (i) Assume for a contradiction that x is dominated by two vertices in C. Without loss of generality, we may assume that these two vertices are v 1 and v i with i < q/2.

, then with the same reasoning v i-3 ∈ N(x). We can repeat this process as long as x → v i+1-2 j . However, this process has to stop since x is not adjacent to v i+2 = v i+1-2 q/2 . Consequently, there exists j such that x ← v i+1-2 j and x → v i+1-2 j for all 0 j < j. But j = 1 for otherwise (v i+1-2 j , x, v i+1 , v i ) is an induced P + (2, 1). Hence, v i-1 → x. Now x does not dominate any vertex v j ∈ V (C)\{v i+1 } for otherwise by the above reasoning both v j-2 and v i-1 would dominate x, a contradiction to (i). Therefore x is a C-twin of v i .

(iii) Assume for a contradiction that x ∈ Reach -(C) and x is not the C-twin of any v i . Let P a be a shortest dipath from x to C. Such a dipath exists because x ∈ Reach -(C), and by (ii), P has length at least 2. Let v i+1 be the terminal vertex of P, u its in-neighbour in P and t the in-neighbour of u in P. The path (t, u, v i+1 , v i ) is a P + (2, 1), which is not induced, so t and v i are adjacent. But t does not dominate v i since P is a shortest dipath from x to C, so v i → t.

Since u dominates v i+1 , we obtain that u is a C-twin of v i by (ii). Therefore C = (v 1 , . . . , v i-1 , u, v i+1 , . . . , v q , v 1 ) is also a directed odd cycle. By (ii), t is a C -twin of v i-1 . In particular, v i-2 → t. This gives a contradiction to (i) as t is dominated by v i-2 and v i . ♦

(2) now clearly follows from Claim 28.1 (iii).

Lemma 30 (iv) this is the only arc between x t-1 and V (H), implying that (x t-1 , x t , v i , v i-1 ) is an induced P + (2, 1), a contradiction.

Lemma 32. Let D be a strong (T T 3 , P + (2, 1))-free oriented graph. If D contains a 5-hole, then χ(D) 4.

) be a 5-hole in D. For i = 1, . . . , 5, define (subscripts are taken modulo 5 all along the proof):

By Lemma 30 (ii)-(iv), the sets X 1 , . . . , X 5 are a partition of the set V (D) \ V (H). Moreover, since D is T T 3 -free, we have:

Claim 32.1. For i = 1, . . . , 5, X i is a stable set, and there is no arc between X i and B i+2 or between X i and A i+3 .

Let π be the colouring of D defined as follows (see Figure 3).

• π(x) = 1 for all x ∈ X 1 ∪ A 4 ∪ B 2 ;

• π(x) = 2 for all x ∈ A 5 ∪C 5 ;

• π(x) = 3 for all x ∈ X 3 ∪ B 5 ;

• π(x) = 4 for all x ∈ A 2 ∪ B 4 ∪C 4 .

By Claim 32.1, π is a proper colouring of D -C 2 .

For any v ∈ C 2 , set π(v) = 4 if v has a neighbour in C 5 , and π(v) = 2 otherwise. We shall prove that the function π is a proper colouring of D. By Claim 32.1, if v ∈ C 2 has no neighbour in C 5 , then none of its neighbours is coloured 2. So the only problem that might occur is if a vertex of v ∈ C 2 coloured with 4 (and thus adjacent to a vertex u ∈ C 5 ) has a neighbour with colour 4, say w. By Claim 32.1, w ∈ C 4 and since D is T T 3 -free, vu and wv are arcs of D.

If u and w were non-adjacent, then (w, v, u, v 4 ) would be an induced P + (2, 1). So they are adjacent and u dominates w, since (u, v, w) cannot induce a T T 3 . But then (v 2 , v 3 , w, u) is an induced P + (2, 1), a contradiction. This proves that π is a proper colouring of D and then χ(D) 4.