Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture

Alex Scott, Paul Seymour

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

A class of graphs is χ-bounded if there is a function f such that χ(G)≤f(ω(G)) for every induced subgraph G of every graph in the class, where χ,ω denote the chromatic number and clique number of G respectively. In 1987, Gyárfás conjectured that for every c, if C is a class of graphs such that χ(G)≤ω(G)+c for every induced subgraph G of every graph in the class, then the class of complements of members of C is χ-bounded. We prove this conjecture. Indeed, more generally, a class of graphs is χ-bounded if it has the property that no graph in the class has c+1 odd holes, pairwise disjoint and with no edges between them. The main tool is a lemma that if C is a shortest odd hole in a graph, and X is the set of vertices with at least five neighbours in V(C), then there is a three-vertex set that dominates X.

Original languageEnglish (US)
Pages (from-to)43-55
Number of pages13
JournalJournal of Combinatorial Theory. Series B
Volume142
DOIs
StatePublished - May 2020

All Science Journal Classification (ASJC) codes

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

Keywords

  • Chromatic number
  • Cliques
  • Induced subgraphs
  • χ-bounded

Fingerprint Dive into the research topics of 'Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture'. Together they form a unique fingerprint.

  • Cite this