-bounded families of oriented graphs

被引:5
作者
Aboulker, P. [1 ,2 ]
Bang-Jensen, J. [3 ]
Bousquet, N. [4 ]
Charbit, P. [5 ,6 ]
Havet, F. [1 ,2 ]
Maffray, F. [7 ,8 ]
Zamora, J. [9 ]
机构
[1] UNSA, CNRS, Project Coati, I3S, Sophia Antipolis, France
[2] INRIA, Sophia Antipolis, France
[3] Univ Southern Denmark, Dept Math & Comp Sci, Odense, Denmark
[4] Ecole Cent Lyon, LIRIS, Ecully, France
[5] Univ Paris Diderot, IRIF, Paris, France
[6] INRIA, Project Gang, Paris, France
[7] CNRS, G SCOP, Grenoble, France
[8] Univ Grenoble Alpes, Grenoble, France
[9] Univ Andres Bello, Dept Matemat, Santiago, Chile
关键词
chromatic number; clique number; -bounded; LARGE CHROMATIC NUMBER; TREES; DIGRAPHS;
D O I
10.1002/jgt.22252
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A famous conjecture of Gyarfas and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets P of orientations of P-4 (the path on four vertices) similar statements hold. We establish some positive and negative results.
引用
收藏
页码:304 / 326
页数:23
相关论文
共 28 条
[1]   Oriented trees in digraphs [J].
Addario-Berry, Louigi ;
Havet, Frederic ;
Sales, Claudia Linhares ;
Reed, Bruce ;
Thomasse, Stephan .
DISCRETE MATHEMATICS, 2013, 313 (08) :967-974
[2]  
Bang-Jensen J., 2008, SPRINGER MONOGR MATH
[3]   On colouring the nodes of a network [J].
Brooks, RL .
PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197
[4]  
Burr S.A., 1980, C NUMER, V28, P227
[5]   K4-free graphs with no odd holes [J].
Chudnovsky, Maria ;
Robertson, Neil ;
Seymour, Paul ;
Thomas, Robin .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (03) :313-331
[6]   The strong perfect graph theorem [J].
Chudnovsky, Maria ;
Robertson, Neil ;
Seymour, Paul ;
Thomas, Robin .
ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229
[7]  
Chvatal V., 1984, Ann. Discrete Math, P63
[8]  
ERDOS P, 1964, CAN MATH B, V7, P351
[9]  
Erds P., 1959, Canadian J. Math., V11, P34
[10]  
Erds P., 1976, THEORY GRAPHS, P83