Coloring of ($P_5$, $4$-wheel)-free graphs

Abstract

For a graph $G$, $\chi (G)$ $(\omega (G))$ denote its chromatic (clique) number. A $P_5$ is the chordless path on five vertices, and a $4$-$wheel$ is the graph consisting of a chordless cycle on four vertices $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. In this paper, we show that every ($P_5$, $4$-wheel)-free graph $G$ satisfies $\chi (G)\le \frac{3}{2}\omega (G)$. Moreover, this bound is almost tight. That is, there is a class of ($P_5$, $4$-wheel)-free graphs $\mathcal{L}$ such that every graph $H\in \mathcal{L}$ satisfies $\chi (H)\ge \frac{10}{7}\omega (H)$. This generalizes/improves several previously known results in the literature.

Revised compact version; Accepted for publication in Discrete Mathematics