New classes of Berge perfect graphs (Q1332433)

Chvátal proved the star-cutset lemma saying that no maximal imperfect graph has a star-cutset. Using a notion of reducible clique and a special type of derived graph \(G| K\) (for a set \(K\subset V)\), \textit{A. Sassano} [Reducible cliques and the strong perfect graph conjecture, IASI Tech. Report R 257 (1989)] proved the following: If \(\mathcal G\) is a hereditary class of Berge graphs in which each minimal imperfect graph \(G\) has a reducible clique \(K\) of size \(\omega(G)\) such that \(G| K\) is also in \(\mathcal G\), then every graph in \(\mathcal G\) is perfect. In this paper, the authors prove that if \(e\) is an edge not belonging to any triangle of a minimal imperfect Berge graph \(G\), then \(G-e\) is also a minimal imperfect Berge graph. The authors prove four classes of Berge graphs to be perfect: The chair is a graph with vertices \(a\), \(b\), \(c\), \(d\), \(e\) and edges \(ab\), \(bc\), \(cd\), \(be\). The graph \(F_ 2\) is obtained from a triangle by attaching a \(P_ 2\) at one vertex and a \(P_ 3\) at another vertex (or has vertices \(a\), \(b\), \(c\), \(d\), \(e\), \(f\) and edges \(ab\), \(bc\), \(ca\), \(ad\), \(be\), \(ef\)). \(G_ 0\) is the graph \(P_ 4\cup K_ 1\) and \(G_ 1\) is obtained from a diamond by attaching a pendant edge at a vertex of degree 2. \(H\) is the graph \(C_ 4\cup K_ 1\). Result 1: Every chair-free and \(F_ 2\)-free Berge graph is perfect. Result 2: Every \(P_ 5\)-free and \(K_{2,3}\)-free Berge graph is perfect. Result 4: Every \(G_ 0\)-free and \(G_ 1\)-free Berge graph is perfect. Result 5: Every \(\overline C_ 4\)-free and \(H\)-free Berge graph is perfect. The first two are proved using the star-cutset lemma, the third using Sassano's result and the fourth using the authors' result quoted above. All but one of the above classes of graphs are \(\overline C_ 4\)-free. Thus considerable progress is achieved towards proving \(\overline C_ 4\)-free Berge graphs to be perfect.