The Strong Perfect Graph Theorem
Maria Chudnovsky, Princeton University

Abstract:
A graph is called perfect if for every induced subgraph the size of its largest clique equals the minimum number of colors needed to color its vertices. In 1960's Claude Berge made a conjecture that has become known as The Strong Perfect Graph Conjecture: any graph that contains no induced odd cycles of length greater than three or their complements is perfect. We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. Some classic examples of perfect graphs are bipartite graphs, complements of bipartite graphs, line graphs of bipartite graphs, and their complements. It has been conjectured that any Berge graph either belongs to one of these four basic classes or can be decomposed in certain ways into smaller basic pieces. Recently we have been able to prove a statement similar to that, except that we need five basic classes instead of four, and consequently, the Strong Perfect Graph Theorem.

This is joint work with Neil Robertson, Paul Seymour and Robin Thomas.