| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
$χ$-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.
Cited literature [35 references]
https://hal.inria.fr/hal-01882395
Contributor : Frederic Havet <>
Submitted on : Friday, December 21, 2018 - 8:59:49 AM
Last modification on : Thursday, November 19, 2020 - 1:12:04 PM
Long-term archiving on: : Friday, March 22, 2019 - 4:03:44 PM
Contributor : Frederic Havet <>
Submitted on : Friday, December 21, 2018 - 8:59:49 AM
Last modification on : Thursday, November 19, 2020 - 1:12:04 PM
Long-term archiving on: : Friday, March 22, 2019 - 4:03:44 PM
File
Induced-digraphs-revised.pdf
Files produced by the author(s)