Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

χ-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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01412667
Contributor : Frederic Havet <>
Submitted on : Thursday, December 8, 2016 - 3:56:27 PM
Last modification on : Wednesday, October 14, 2020 - 4:19:20 AM
Long-term archiving on: : Thursday, March 23, 2017 - 8:01:30 AM

File

chiboundDMay17.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

988

Files downloads

282