An optimal chromatic bound for the class of $\{P_3\cup 2K_1,\overline{P_3\cup 2K_1}\}$-free graphs

Abstract

In 1987, A. Gyárfás in his paper ``Problems from the world surrounding perfect graphs'' posed the problem of determining the smallest $\chi$-binding function for $\mathcal{G}(F,\overline{F})$, when $\mathcal{G}(F)$ is $\chi$-bounded. So far the problem has been attempted for only forest $F$ with four or five vertices. In this paper, we address the case when $F=P_3\cup 2K_1$ and show that if $G$ is a $\{P_3\cup 2K_1,\overline{P_3\cup 2K_1}\}$-free graph with $\omega (G)\ne 3$, then it admits $\omega (G)+1$ as a $\chi$-binding function. Moreover, we also construct examples to show that this bound is tight for all values of $\omega \ne 3$.