Decomposing Berge graphs containing no proper wheel, long prism or their complements (Q879162)

A graph is said to be perfect if, in all its induced subgraphs, the size of a largest clique is equal to the chromatic number and a graph is said to be Berge if it does not contain an odd hole or its complement. The strong perfect graph conjecture (SPGC) states that Berge graphs are perfect. In this paper it is shown that, if \(G\) is a Berge graph such that neither \(G\) nor its complement \(\overline{G}\) contains certain induced subgraphs, named proper wheels and long prisms (described in the paper), then either \(G\) is a basic perfect graph (a bipartite graph, a line graph of a bipartite graph or the complement of such graphs) or it has a skew partition that cannot occur in a minimally imperfect graph. This structural result implies that \(G\) is perfect. Note that this paper has been submitted in May 2002 and revised in November 2003 and \textit{M. Chudnovsky, N. Robertson, P. Seymour} and \textit{R. Thomas} simultaneously (June 2002) [Ann. Math. (2) 164, No. 1, 51--229 (2006; Zbl 1112.05042)] proved a similar result; finally they also showed that no minimally imperfect Berge graph satisfies the following property: \(G\) contains a proper wheel but neither \(G\) nor \(\overline{G}\) contains a long prism, thus solving the SPGC.