The Perfect Graph Theorem

A graph is said to be perfect if the chromatic number of every induced subgraph equals its clique number. An induced cycle of size 4 or more is called a hole and an induced subgraph that is the complement of a cycle of size 4 or more is called an antihole. A Berge graph is a graph without any odd hole or odd antihole.

The strong perfect graph theorem states that a graph is perfect if and only if it is Berge. It was conjectured by Claude Berge in 1961, and proved by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas. The four authors presented their work at a workshop held from Oct 30 to Nov 3, 2002 at the American Institute of Mathematics and published a 178-page paper in 2006.

For the purpose of this talk, however, we will be slightly modest and discuss a proof of the weak perfect graph theorem, which states that if a graph is perfect, then so is its complement. Also conjectured by Berge, it was proved by Lovasz in 1972.