Contents Online

# Journal of Combinatorics

## Volume 4 (2013)

### Number 3

### Complements of nearly perfect graphs

Pages: 299 – 310

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n3.a2

#### Authors

#### Abstract

A class of graphs closed under taking induced subgraphs is $\chi$-bounded if there exists a function $f$ such that for all graphs $G$ in the class, $\chi(G) \leq f(\omega(G))$. We consider the following question initially studied in [A. Gyárfás, Problems from the world surrounding perfect graphs, *Zastowania Matematyki Applicationes Mathematicae*, 19:413–441, 1987]. For a $\chi$-bounded class $\cal C$, is the class $\overline{C}$ $\chi$-bounded (where $\overline{\cal C}$ is the class of graphs formed by the complements of graphs from $\cal C$)? We show that if $\cal C$ is $\chi$-bounded by the constant function $f(x)=3$, then $\overline{\cal C}$ is $\chi$-bounded by $g(x)=\lfloor\frac{8}{5}x\rfloor$ and this is best possible.

We show that for every constant $c>0$, if $\cal C$ is $\chi$-bounded by a function $f$ such that $f(x)=x$ for $x \geq c$, then $\overline{\cal C}$ is $\chi$-bounded. For every $j$, we construct a class of graphs $\chi$-bounded by $f(x)=x+x/\log^j(x)$ whose complement is not $\chi$-bounded.

Published 13 August 2013