Complements of nearly perfect graphs

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)\le f(\omega (G))$. We consider the following question initially studied in [A. Gy{á}rf{á}s, Problems from the world surrounding perfect graphs, {\em Zastowania Matematyki Applicationes Mathematicae}, 19:413--441, 1987]. For a $\chi$-bounded class $\mathcal{C}$, is the class $\bar{C}$ $\chi$-bounded (where $\bar{\mathcal{C}}$ is the class of graphs formed by the complements of graphs from $\mathcal{C}$)? We show that if $\mathcal{C}$ is $\chi$-bounded by the constant function $f(x)=3$, then $\bar{\mathcal{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 $\mathcal{C}$ is $\chi$-bounded by a function $f$ such that $f(x)=x$ for $x\ge c$, then $\bar{\mathcal{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.