χ-bounded families of oriented graphs - Archive ouverte HAL Access content directly
Journal Articles Journal of Graph Theory Year : 2018

## χ-bounded families of oriented graphs

(1) , (2) , (3) , (4, 5) , (1) , (3) , (6)
1
2
3
4
5
6
Pierre Aboulker
Jørgen Bang-Jensen
• Function : Author
Nicolas Bousquet
Frédéric Havet
Frédéric Maffray
Jose Zamora
• Function : Author

#### 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.

#### Domains

Computer Science [cs] Discrete Mathematics [cs.DM]

### Dates and versions

hal-01882395 , version 1 (21-12-2018)

### Identifiers

• HAL Id : hal-01882395 , version 1
• DOI :

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

208 View