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

András Gyárfás (Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary)

Zhentao Li (École Normale Supérieure de Lyon, LIP, Lyon, France)

Raphael Machado (Inmetro, Rio de Janeiro, Brazil)

András Sebő (CNRS, Grenoble-INP, UJF, Laboratoire G-SCOP, Equipe Optimisation Combinatoire, Grenoble, France)

Stéphan Thomassé (École Normale Supérieure de Lyon, LIP, Lyon, France)

Nicolas Trotignon (École Normale Supérieure de Lyon, LIP, Lyon, France)

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.

Full Text (PDF format)