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

Maria Chudnovsky; Alex Scott; Paul Seymour

doi:10.1016/j.ejc.2018.09.003

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

Maria Chudnovsky, Alex Scott, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

11 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 language	English (US)
Pages (from-to)	53-61
Number of pages	9
Journal	European Journal of Combinatorics
Volume	76
DOIs	https://doi.org/10.1016/j.ejc.2018.09.003
State	Published - Feb 2019

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2018.09.003

Cite this

@article{900cc1c273094900afd6d697c881539e,

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{\"o}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.",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Ltd",

year = "2019",

month = feb,

doi = "10.1016/j.ejc.2018.09.003",

language = "English (US)",

volume = "76",

pages = "53--61",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

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

SN - 0195-6698

VL - 76

SP - 53

EP - 61

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this