On forbidden induced subgraphs for K_{1,3}-free perfect graphs

Abstract

Considering connected $K_{1,3}$-free graphs with independence number at least $3$, Chudnovsky and Seymour (2010) showed that every such graph, say $G$, is $2\omega$-colourable where $\omega$ denotes the clique number of $G$. We study $(K_{1,3},Y)$-free graphs, and show that the following three statements are equivalent. (1) Every connected $(K_{1,3},Y)$-free graph which is distinct from an odd cycle and which has independence number at least $3$ is perfect. (2) Every connected $(K_{1,3},Y)$-free graph which is distinct from an odd cycle and which has independence number at least $3$ is $\omega$-colourable. (3) $Y$ is isomorphic to an induced subgraph of $P_5$ or $Z_2$ (where $Z_2$ is also known as hammer). Furthermore, for connected $(K_{1,3},Y)$-free graphs (without an assumption on the independence number), we show a similar characterisation featuring the graphs $P_4$ and $Z_1$ (where $Z_1$ is also known as paw).