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

Abstract

A class of graphs is $χ$-bounded if there is a function $f$ such that $χ(G)\le 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 $\mathcal{C}$ is a class of graphs such that $χ(G)\le ω(G)+c$ for every induced subgraph $G$ of every graph in the class, then the class of complements of members of $\mathcal{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$.