Optimal chromatic bound for ($P_2+P_3$, $\overline{P_2+P_3}$)-free graphs

Abstract

For a graph $G$, let $\chi (G)$ ($\omega (G)$) denote its chromatic (clique) number. A $P_2+P_3$ is the graph obtained by taking the disjoint union of a two-vertex path $P_2$ and a three-vertex path $P_3$. A $\overline{P_2+P_3}$ is the complement graph of a $P_2+P_3$. In this paper, we study the class of ($P_2+P_3$, $\overline{P_2+P_3}$)-free graphs and show that every such graph $G$ with $\omega (G)\ge 3$ satisfies $\chi (G)\le \max \{\omega (G)+3,\lfloor \frac{3}{2}\omega (G)\rfloor -1\}$. Moreover, the bound is tight. Indeed, for any $k\in \mathbb{N}$ and $k\ge 3$, there is a ($P_2+P_3$, $\overline{P_2+P_3}$)-free graph $G$ such that $\omega (G)=k$ and $\chi (G)=\max \{k+3,\lfloor \frac{3}{2}k\rfloor -1\}$.