The chromatic number of (P_5, HVN )-free graphs

Abstract

Let $G$ be a graph. We use $\chi (G)$ and $\omega (G)$ to denote the chromatic number and clique number of $G$ respectively. A $P_5$ is a path on 5 vertices, and an $HVN$ is a $K_4$ together with one more vertex which is adjacent to exactly two vertices of $K_4$. Combining with some known result, in this paper we show that if $G$ is $(P_5,\text{HVN})$-free, then $\chi (G)\le \max \{\min \{16,\omega (G)+3\},\omega (G)+1\}$. This upper bound is almost sharp.