The Strong Perfect Graph Theorem

A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest clique of H. A graph G is Berge if no induced subgraph of G is an odd cycle of legth at least 5 or the complement of one. The "Strong Perfect Graph Conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. Perfect graphs are relevant to linear, integer and semi-definite programming, communication theory, geometric algorithms and other areas. The SPGC is arguably the most important open problem in graph theory.

Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas recently proved the SPGC. I will present an ouline of their proof, after giving a history of perfect graphs and the SPGC.