On the chromatic number of (P5,windmill)-free graphs

Abstract

In this paper we study the chromatic number of $(P_{5},windmill)$-free graphs. For integers $r,p\geq 2$ the windmill graph $W_{r+1}^p=K_1 \vee pK_r$ is the graph obtained by joining a single vertex (the center) to the vertices of $p$ disjoint copies of a complete graph $K_r$. Our main result is that every $(P_{5},windmill)$-free graph $G$ admits a polynomial $\chi$-binding function. Moreover, we will present polynomial $\chi$-binding functions for several other subclasses of $P_{5}$-free graphs.