Chair-free Berge graphs are perfect (Q1376074)

A chair is a graph with nodes \(a,b,c,d,e\) and edges \(ab,bc, cd,be\). The author proves that the strong perfect graph conjecture is true for chair-free graphs. The proof technique uses the properties of minimal imperfect graphs (MIGs) dicovered by Lovász, Padberg, Chvátal, and Sebő and the reduction operation introduced by Lovász and Plummer. If \(C\) is a maximal clique in a graph \(G=(V,E)\), the reduction of \(G\) with respect to \(C\) is the graph \(G|C=(V|C, E|C)\) where \(V|C=V-C\) and \(E|C= (E-\{uv\in E\mid u\in C\}) \cup \{uv\mid \{u,v\} \subseteq V-C\) and \(N_G(\{u,v\}) \supseteq C\} \). Further, \(C\) is reducible in \(G\) iff \(\alpha (G|C)= \alpha (G)-1\). Some of the important steps in the long proof are: (1) If \(G\) is a MIG with \(\alpha (G)\geq 3\) and \(C\) is a reducible clique of size \(\omega\) in \(G\), then \(G|C\) is an imperfect graph. (2) Every chair-free MIG has a reducible clique of size \(\omega\). (3) If \(C\) is a reducible clique in a chair-free graph \(G\) without odd holes, then \(G|C\) contains no odd hole. (4) If \(C\) is a reducible clique in a chair-free MIG \(H\) which is also Berge, and \(H'\) is a minimal imperfect subgraph of \(H|C\) which is also Berge, then \(H'\) is chair-free.