Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We prove a conjecture of András Gyárfás, that for all κ,ℓ, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ.

Original languageEnglish (US)
Pages (from-to)84-97
Number of pages14
JournalJournal of Combinatorial Theory. Series B
Volume140
DOIs
StatePublished - Jan 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes'. Together they form a unique fingerprint.

  • Cite this