A survey of χ-boundedness

Alex Scott, Paul Seymour

Research output: Contribution to journalArticle

Abstract

If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

Original languageEnglish (US)
Pages (from-to)473-504
Number of pages32
JournalJournal of Graph Theory
Volume95
Issue number3
DOIs
StateAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • colouring
  • χ-boundedness

Fingerprint Dive into the research topics of 'A survey of χ-boundedness'. Together they form a unique fingerprint.

  • Cite this