Paper Info
Title
Induced subgraphs of graphs with large chromatic number. XI. Orientations.
Abstract
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.
Year
DOI
Venue
2019
10.1016/j.ejc.2018.09.003
European Journal of Combinatorics
Field
DocType
Volume
Graph,Discrete mathematics,Combinatorics,Clique number,Chromatic scale,Isomorphism,Mathematics,Digraph,Bounded function
Journal
76
ISSN
Citations 
PageRank 
0195-6698
0
0.34
References 
Authors
4
3
Name
Order
Citations
PageRank
Maria Chudnovsky139046.13
Alex Scott225140.93
Paul D. Seymour32786314.49