$χ$-bounded families of oriented graphs

P. Aboulker 1 J. Bang-Jensen 2 Nicolas Bousquet 3 Pierre Charbit 4, 5 Frédéric Havet 1 F. Maffray 3 J. Zamora 6
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
3 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
5 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : 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.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2018, 89 (3), pp.304 - 326. 〈10.1002/jgt.22252〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01882395
Contributeur : Frederic Havet <>
Soumis le : vendredi 21 décembre 2018 - 08:59:49
Dernière modification le : vendredi 4 janvier 2019 - 17:33:38

Fichier

Induced-digraphs-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

P. Aboulker, J. Bang-Jensen, Nicolas Bousquet, Pierre Charbit, Frédéric Havet, et al.. $χ$-bounded families of oriented graphs. Journal of Graph Theory, Wiley, 2018, 89 (3), pp.304 - 326. 〈10.1002/jgt.22252〉. 〈hal-01882395〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

91