Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4 (Q2124634)

Given a graph \(G\) and a set \(S\) of its vertices, we call a graph \(H\) an induced subgraph of \(G\) if there is a set of vertices of \(G\) which induces a graph isomorphic to \(H\). Given a family \(\mathcal{H}\) of graphs and a graph \(G\), we say that \(G\) is \(\mathcal{H}\)-free if \(G\) contains no graph from \(\mathcal{H}\) as an induced subgraph. \textit{M. Chudnovsky} and \textit{P. Seymour} [J. Comb. Theory, Ser. B 100, No. 6, 560--572 (2010; Zbl 1207.05050)] proved that the chromatic number of connected \(K_{1,3}\)-free graphs with independence number at least 3 is at most twice as large as the clique number, and they also presented an infinite family of such graphs whose chromatic number is almost this large. In the present paper, the authors consider the class of all connected \(\{K_{1,3},X\}\)-free graphs which are distinct from an odd cycle and have an independence number of at least 4. They deduce that all graphs in the class are perfect if and only if \(X\) is an induced subgraph of some of \(P_6\), \(K_1\cup P_5\), \(2P_3\), \(Z_2\) or \(K_1\cup Z_1\). Furthermore, the authors list all eight imperfect graphs belonging to the class when \(X=2K_1\cup K_3\), and prove that there are infinitely many such graphs for every other choice of \(X\). Finally, they describe the structure of all imperfect graphs in the class for \(X=B_{1,2}\).