Chromatic bounds for some classes of $2K_2$-free graphs

Abstract

A hereditary class $\mathcal{G}$ of graphs is $\chi$-bounded if there is a $\chi$-binding function, say $f$ such that $\chi (G)\le f(\omega (G))$, for every $G\in \mathcal{G}$, where $\chi (G)$ ($\omega (G)$) denote the chromatic (clique) number of $G$. It is known that for every $2K_2$-free graph $G$, $\chi (G)\le \left(\genfrac{}{}{0ex}{}{\omega (G)+1}{2}\right)$, and the class of ($2K_2,3K_1$)-free graphs does not admit a linear $\chi$-binding function. In this paper, we are interested in classes of $2K_2$-free graphs that admit a linear $\chi$-binding function. We show that the class of ($2K_2,H$)-free graphs, where $H\in \{K_1+P_4,K_1+C_4,\overline{P_2\cup P_3},HVN,K_5-e,K_5\}$ admits a linear $\chi$-binding function. Also, we show that some superclasses of $2K_2$-free graphs are $\chi$-bounded.

Revised version