Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ.

Original languageEnglish (US)
Pages (from-to)109-128
Number of pages20
JournalJournal of Combinatorial Theory. Series B
Volume118
DOIs
StatePublished - May 1 2016

All Science Journal Classification (ASJC) codes

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

Keywords

  • Colouring
  • Holes
  • Induced subgraph
  • χ-Bounded

Fingerprint Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures'. Together they form a unique fingerprint.

Cite this