### 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 | English (US) |
---|---|

Pages (from-to) | 43-55 |

Number of pages | 13 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 142 |

DOIs | |

State | Published - 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