Opuscula Math. 37, no. 4 (2017), 609-615
http://dx.doi.org/10.7494/OpMath.2017.37.4.609

Opuscula Mathematica

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

Ingo Schiermeyer

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.

Keywords: vertex colouring, perfect graphs, $$\chi$$-binding function, forbidden induced subgraph.

Mathematics Subject Classification: 05C15, 05C17.

Full text (pdf)