, Case 2: no neighbour of c in L 0 belongs to an odd hole in L 0

, By Lemma 30 (iii), 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, 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, vol.31

, Let w ? B i and w be a neighbour of w in L 0

, Since N L 0 (B i ) is complete to N L 0 (A i ), I = {1,. .. , k} and 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

L. Addario-berry, F. Havet, C. L. Sales, B. A. Reed, and S. Thomassé, Oriented trees in digraphs, Discrete Mathematics, vol.313, issue.8, pp.967-974
URL : https://hal.archives-ouvertes.fr/inria-00551133

J. Bang-jensen and G. Gutin, Oriented trees in digraphs, Digraphs: Theory, Algorithms and Applications, 2008.

R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc, vol.37, pp.194-197, 1941.

S. A. Burr, Subtrees of directed graphs and hypergraphs, Proceedings of the 11th Southeastern Conference on Combinatorics, Graph theory and Computing, pp.227-239, 1980.

M. Chudnovsky, N. Robertson, P. D. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. of Math, vol.164, issue.2, pp.51-229, 2006.

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, K 4-free graphs with no odd holes, J. Combinatorial Theory, Ser. B, vol.100, pp.313-331, 2010.

V. , Perfectly ordered graphs, Topics on perfect graphs, vol.21, pp.63-65, 1984.

P. Erd?, Graph theory and probability, Canad. J. Math, vol.11, pp.34-38, 1959.

P. Erd?-os and A. Hajnal, On the chromatic number of infinite graphs, Theory of Graphs, Proceedings of the 1966 Colloquium at Tihany, pp.83-98, 1976.

P. Erd?-os and L. Moser, A problem on tournaments, Canad. Math. Bull, vol.7, issue.4, pp.351-356, 1964.

H. Galeana-sánchez, I. A. Goldfeder, and I. Urrutia, On the structure of strong 3-quasitransitive digraphs, Discrete Mathematics, vol.310, pp.2495-2498, 2010.

T. Gallai, On directed paths and circuits, Theory of Graphs (Proc. Colloq. Titany, 1966), pp.115-118, 1968.

A. Ghouila, Houri Caractérisation des graphes non orientes dont on peut orienter les aretes de manierè a obtenir le graphe d'une rélation d'ordre. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, vol.254, pp.1370-1371, 1962.

A. Gyárfás, On ramsey covering-numbers. In Infinite and Finite Sets, Coll. Math. Soc. János Bolyai, p.10, 1975.

A. Gyárfás, Problems from the world surrounding perfect graphs, Zastowania Matematyki Applicationes Mathematicae, pp.413-441, 1987.

A. Gyárfás, E. Szemerédi, and Z. Tuza, Induced subtrees in graphs of large chromatic number, Discrete Math, vol.30, pp.235-244, 1980.

M. Hasse, Zur algebraischen bergründ der graphentheorie I, Math. Nachr, vol.28, pp.275-290, 1964.

C. C. Harner and R. C. , Entringer Arc colorings of digraphs, Journal of Combinatorial Theory, Series B, vol.13, issue.3, pp.219-225, 1972.

H. A. Kierstead and S. G. Penrice, Radius two trees specify ?-bounded classes, J. Graph Theory, vol.18, pp.119-129, 1994.

H. A. Kierstead and V. Rödl, Applications of hypergraph colouring to colouring graphs that do not induce certain trees, Discrete Math, vol.150, pp.187-193, 1996.

H. A. Kierstead and W. T. Trotter, Colorfull induced subgraphs, Discrete Math, vol.101, pp.165-169, 1992.

B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory, vol.43, issue.2, pp.107-116, 2003.

V. N. Lara, The dichromatic number of a digraph, J. Combin. Theory Ser. B, vol.33, issue.3, pp.265-270, 1982.

F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc, vol.30, pp.264-286, 1930.

B. Roy, Nombre chromatique et plus longs chemins d'un graphe. Rev. Francaise Informat, Recherche Opérationnelle, vol.1, issue.5, pp.129-132, 1967.

J. Schmerl, Recursion theoretic aspect of graphs and orders, The theory and application of graphs, pp.467-484, 1985.

A. D. Scott, Induced trees in graphs of large chromatic number, J. Graph Theory, vol.24, pp.297-311, 1997.

A. D. Scott and P. D. Seymour, Colouring graphs with no odd holes

D. P. Sumner, Subtrees of a graph and the chromatic number, The theory and applications of graphs, pp.557-576, 1980.

L. M. Vitaver, Determination of minimal colouring of vertices of a graph by means of boolean powers of the incidence matrix, Doklady Akademii Nauk SSSR, vol.147, pp.758-759, 1962.

S. Wang and R. Wang, The structure of strong arc-locally in-semicomplete digraphs, Discrete Mathematics, vol.309, pp.6555-6562, 2009.