$\chi$-binding function for a superclass of $2K_2$-free graphs

Abstract

The class of $2K_2$-free graphs has been well studied in various contexts in the past. In this paper, we study the chromatic number of $\{butterfly,hammer\}$-free graphs, a superclass of $2K_2$-free graphs and show that a connected $\{butterfly,hammer\}$-free graph $G$ with $\omega (G)\ne 2$ admits $\left(\genfrac{}{}{0ex}{}{\omega +1}{2}\right)$ as a $\chi$-binding function which is also the best available $\chi$-binding function for its subclass of $2K_2$-free graphs. In addition, we show that if $H\in \{C_4+K_p,P_4+K_p\}$, then any $\{butterfly,hammer,H\}$-free graph $G$ with no components of clique size two admits a linear $\chi$-binding function. Furthermore, we also establish that any connected $\{butterfly,hammer,H\}$-free graph $G$ where $H\in \{(K_1\cup K_2)+K_p,2K_1+K_p\}$, is perfect for $\omega (G)\ge 2p$.