Premium
χ‐bounded families of oriented graphs
Author(s) -
Aboulker P.,
BangJensen J.,
Bousquet N.,
Charbit P.,
Havet F.,
Maffray F.,
Zamora J.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22252
Subject(s) - combinatorics , mathematics , digraph , tournament , conjecture , graph , induced subgraph , discrete mathematics , chromatic scale , transitive relation , bounded function , vertex (graph theory) , mathematical analysis
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.