, 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
Oriented trees in digraphs, Discrete Mathematics, vol.313, issue.8, pp.967-974 ,
URL : https://hal.archives-ouvertes.fr/inria-00551133
Oriented trees in digraphs, Digraphs: Theory, Algorithms and Applications, 2008. ,
On colouring the nodes of a network, Proc. Cambridge Philos. Soc, vol.37, pp.194-197, 1941. ,
Subtrees of directed graphs and hypergraphs, Proceedings of the 11th Southeastern Conference on Combinatorics, Graph theory and Computing, pp.227-239, 1980. ,
The strong perfect graph theorem, Ann. of Math, vol.164, issue.2, pp.51-229, 2006. ,
K 4-free graphs with no odd holes, J. Combinatorial Theory, Ser. B, vol.100, pp.313-331, 2010. ,
Perfectly ordered graphs, Topics on perfect graphs, vol.21, pp.63-65, 1984. ,
Graph theory and probability, Canad. J. Math, vol.11, pp.34-38, 1959. ,
On the chromatic number of infinite graphs, Theory of Graphs, Proceedings of the 1966 Colloquium at Tihany, pp.83-98, 1976. ,
A problem on tournaments, Canad. Math. Bull, vol.7, issue.4, pp.351-356, 1964. ,
On the structure of strong 3-quasitransitive digraphs, Discrete Mathematics, vol.310, pp.2495-2498, 2010. ,
On directed paths and circuits, Theory of Graphs (Proc. Colloq. Titany, 1966), pp.115-118, 1968. ,
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. ,
On ramsey covering-numbers. In Infinite and Finite Sets, Coll. Math. Soc. János Bolyai, p.10, 1975. ,
Problems from the world surrounding perfect graphs, Zastowania Matematyki Applicationes Mathematicae, pp.413-441, 1987. ,
Induced subtrees in graphs of large chromatic number, Discrete Math, vol.30, pp.235-244, 1980. ,
Zur algebraischen bergründ der graphentheorie I, Math. Nachr, vol.28, pp.275-290, 1964. ,
Entringer Arc colorings of digraphs, Journal of Combinatorial Theory, Series B, vol.13, issue.3, pp.219-225, 1972. ,
Radius two trees specify ?-bounded classes, J. Graph Theory, vol.18, pp.119-129, 1994. ,
Applications of hypergraph colouring to colouring graphs that do not induce certain trees, Discrete Math, vol.150, pp.187-193, 1996. ,
Colorfull induced subgraphs, Discrete Math, vol.101, pp.165-169, 1992. ,
Circular colorings of edge-weighted graphs, J. Graph Theory, vol.43, issue.2, pp.107-116, 2003. ,
The dichromatic number of a digraph, J. Combin. Theory Ser. B, vol.33, issue.3, pp.265-270, 1982. ,
On a problem of formal logic, Proc. London Math. Soc, vol.30, pp.264-286, 1930. ,
Nombre chromatique et plus longs chemins d'un graphe. Rev. Francaise Informat, Recherche Opérationnelle, vol.1, issue.5, pp.129-132, 1967. ,
Recursion theoretic aspect of graphs and orders, The theory and application of graphs, pp.467-484, 1985. ,
Induced trees in graphs of large chromatic number, J. Graph Theory, vol.24, pp.297-311, 1997. ,
Colouring graphs with no odd holes ,
Subtrees of a graph and the chromatic number, The theory and applications of graphs, pp.557-576, 1980. ,
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. ,
The structure of strong arc-locally in-semicomplete digraphs, Discrete Mathematics, vol.309, pp.6555-6562, 2009. ,