On minimal imperfect graphs without induced \(P_5\) (Q1293187)

This paper deals with \(P_5\)-free minimal imperfect graphs and Berge's strong perfect graph conjecture. If \(G\) is a graph then \(\chi(G)\) is the chromatic number of \(G\) and \(\omega(G)\) is the cardinality of a maximum clique of \(G\). A graph \(G\) is perfect if \(\chi(H)=\omega(H)\) for every induced subgraph \(H\) of \(G\). The Strong Perfect Graph Conjecture (SPGC) states that a graph is perfect if and only if it does not contain an odd hole or an odd anti-hole as an induced subgraph. The main result of this paper is that SPGC holds for the \((P_5,F)\)-free graphs whenever \(F\) is any connected configuration on five vertices not containing an induced \(2K_2\). The authors give a detained summary of previous known results on \(P_5\)-free minimal imperfect graphs. They then introduce two new classes of graphs (which contain \(P_5\)-free graphs) and show that most of the results concerning \(P_5\)-free graphs can be extended to these classes. A structural characterization for these classes is given which then leads to the proof that SPGC is true for the \((P_5,F)\)-free graphs mentioned above.