Induced subgraphs of graphs with large chromatic number. I. Odd holes

Alex Scott, Paul Seymour

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture.

Original languageEnglish (US)
Pages (from-to)68-84
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume121
DOIs
StatePublished - Nov 1 2016

All Science Journal Classification (ASJC) codes

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

Keywords

  • Colouring
  • Induced subgraphs
  • Odd holes

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

  • Cite this