Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

We prove a 1985 conjecture of Gyárfás that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ.

Original languageEnglish (US)
Pages (from-to)1057-1072
Number of pages16
JournalCombinatorica
Volume37
Issue number6
DOIs
StatePublished - Dec 1 2017

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes'. Together they form a unique fingerprint.

  • Cite this