Induced subgraphs of graphs with large chromatic number. XI. Orientations

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)53-61
Number of pages9
JournalEuropean Journal of Combinatorics
Volume76
DOIs
StatePublished - Feb 2019

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. XI. Orientations'. Together they form a unique fingerprint.

Cite this