TY - JOUR
T1 - Induced subgraphs of graphs with large chromatic number. XI. Orientations
AU - Chudnovsky, Maria
AU - Scott, Alex
AU - Seymour, Paul
PY - 2019/2
Y1 - 2019/2
N2 - Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H? Kierstead and Rödl (1996) raised this question for two specific kinds of digraph H: the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al. (2018) subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions.
AB - Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H? Kierstead and Rödl (1996) raised this question for two specific kinds of digraph H: the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al. (2018) subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions.
UR - http://www.scopus.com/inward/record.url?scp=85054421583&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85054421583&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2018.09.003
DO - 10.1016/j.ejc.2018.09.003
M3 - Article
AN - SCOPUS:85054421583
VL - 76
SP - 53
EP - 61
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
SN - 0195-6698
ER -