The strong perfect graph conjecture holds for diamonded odd cycle-free graphs (Q1208345)

Let \(G_ 5=P_ 4\lor K_ 1\) and \(J_ 5=C_ 4\lor K_ 1\). The authoress defines an odd cycle \(C\) of a (simple) graph \(G\) to be a diamonded odd cycle if \(C\) induces \(G_ 5\) or \(J_ 5\) or if \(C\) has length more than five and two chords \(xy,xz\) with \(yz\) an edge of \(C\) and there is a vertex \(w\) not on \(C\), adjacent to \(y\) and \(z\) but not \(x\) and there is no edge of \(C\) (other than \(yz)\) which lies on a triangle induced by the vertices of \(C\). She then proves that the strong perfect graph conjecture is true for graphs which do not contain a diamonded odd cycle. The main technique of proof is to go from the graph \(G\) to its clique- vertex incidence matrix \(M\) and then to the bipartite graph \(H\) for which \(M\) is the adjacency matrix between the vertices of the two parts \(S\) and \(T\) of the vertex set of \(H\). The vertices in \(S\) and \(T\) correspond to the cliques and vertices of \(G\). Assuming \(G\) to be a minimal imperfect graph without diamonded odd cycles, it is first shown that to verify SPGC (for such graphs) it is enough to show that \(G\) has no odd hole of size five or more. Assuming the contrary, it is eventually proved that \(G\) contains a star cut set, and a theorem of V. Chvátal provides the necessary contradiction. Several new definitions are introduced to effect the translation of the conditions from \(G\) to \(H\) and the recent results of Conforti and Rao on balanced and perfect matrices are extensively used. A clear presentation is achieved by breaking up the steps into several lemmas. Even with this, a monstrous lemma (Lemma 6) leads to several cases, only one of which is presented in full detail. For the others, the authoress's Ph. D. thesis is cited.