TY  - JOUR
ID  - Schiermeyer2017
LB  - Schiermeyer2017
AU  - Schiermeyer, Ingo
TI  - On the chromatic number of (P<sub>5</sub>,windmill)-free graphs
ST  - On the chromatic number of (P<sub>5</sub>,windmill)-free graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2017
VL  - 37
IS  - 4
SP  - 609
EP  - 615
DO  - http://dx.doi.org/10.7494/OpMath.2017.37.4.609
UR  - http://dx.doi.org/10.7494/OpMath.2017.37.4.609
AB  - 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.
KW  - vertex colouring
KW  - perfect graphs
KW  - \(\chi\)-binding function
KW  - forbidden induced subgraph
SN  - 1232-9274
ER  -