χ-bounded families of oriented graphs

Pierre Aboulker (1, 2, 3) , Jørgen Bang-Jensen (4, 3) , Nicolas Bousquet (5) , Pierre Charbit (6) , Frédéric Havet (1, 2, 3) , Frédéric Maffray (7) , Jose Zamora (8)

1 I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
2 COMUE UCA - COMUE Université Côte d'Azur (2015-2019)
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
4 IMADA - Department of Mathematics and Computer Science [Odense]
5 GOAL - Graphes, AlgOrithmes et AppLications
6 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
7 G-SCOP_OC - Optimisation Combinatoire
8 UNAB - Universidad Andrés Bello [Santiago]

A famous conjecture of Gyárfás 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.

Domaines: Mathématique discrète [cs.DM]

Pierre Aboulker, Jørgen Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, et al.. χ-bounded families of oriented graphs. 2016. ⟨hal-01412667⟩