χ-bounded families of oriented graphs

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 :
Pré-publication, Document de travail
2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01412667
Contributeur : Frederic Havet <>
Soumis le : jeudi 8 décembre 2016 - 15:56:27
Dernière modification le : mardi 16 janvier 2018 - 16:25:52
Document(s) archivé(s) le : jeudi 23 mars 2017 - 08:01:30

Fichier

chiboundDMay17.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01412667, version 1
  • ARXIV : 1605.07411

Citation

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

Partager

Métriques

Consultations de la notice

631

Téléchargements de fichiers

51