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 language | American English |
---|---|
Pages (from-to) | 43-55 |
Number of pages | 13 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 142 |
DOIs | |
State | Published - May 2020 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Chromatic number
- Cliques
- Induced subgraphs
- χ-bounded