Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs (Q1405122): Difference between revisions

A hole is a cordless cycle of length at least four. A hole is odd if it has an odd number of vertices. The strong perfect graph conjecture states that a graph \(G\) is perfect if neither \(G\) nor \(\overline G\) has an odd hole. The authors prove the conjecture for graphs that do not contain parachutes and proper wheels. Recently, \textit{M. Chudnovsky}, \textit{N. Robertson}, \textit{P. D. Seymoud} and \textit{R. Thomas} [Math. Program. 97B, 405-422 (2002; Zbl 1028.05035)] proved the conjecture for all graphs.