Induced subgraphs of graphs with large chromatic number. VII. Gyarfas' complementation conjecture

摘要

A class of graphs is chi-bounded if there is a function f such that chi(G) <= f (omega(G)) for every induced subgraph G of every graph in the class, where chi, omega denote the chromatic number and clique number of G respectively. In 1987, Gyarfas conjectured that for every c, if C is a class of graphs such that chi(G) <= omega(G) + c for every induced subgraph G of every graph in the class, then the class of complements of members of C is chi-bounded. We prove this conjecture. Indeed, more generally, a class of graphs is chi-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. (C) 2019 Elsevier Inc. All rights reserved.