Strong perfect graph theorem

Remarks

The complement of an odd hole is called an odd antihole, and graphs with neither are called Berge graphs. The easy direction holds because an odd hole $C_{2k+1}$ with $k \ge 2$ has $\omega = 2$ and $\chi = 3$, and its complement has $\omega = k$ and $\chi = k + 1$. The hard direction was conjectured by Claude Berge and proved by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas, with the proof published in 2006. Their proof shows that every Berge graph lies in one of a few basic classes of perfect graphs or admits one of a few kinds of decomposition. A smallest Berge graph that is not perfect can have neither property. The theorem implies the weak perfect graph theorem, since the condition is symmetric in $G$ and $\overline{G}$.

Going deeper

For a student

The theorem turns a condition about all induced subgraphs into a finite list of forbidden patterns. It was one of the main open problems of graph theory for about forty years. Later work showed that Berge graphs, and hence perfect graphs, can be recognized in polynomial time.