Repository logo

Browsing by Subject "perfect graphs"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    On the chromatic number of (P5,windmill)-free graphs
    (Wydawnictwa AGH, 2017) Schiermeyer, Ingo
    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.