3/5/2003

Paul Seymour
Princeton University

In 1961, Claude Berge proposed the conjecture that, in every graph with no odd hole or odd antihole, the number of colours needed to properly colour the graph equals the size of the largest complete subgraph. (An "odd hole" means an induced subgraph which is an odd cycle of length >= 5, and an "odd antihole" is the same in the complement graph.) This became one of  the most well-known and popular open problems in graph theory. In joint work with Maria Chudnovsky, Neil Robertson and Robin Thomas, we proved the conjecture last summer.

Most previous approaches to the conjecture were based on studying properties of a minimal counterexample, but our approach was different.  We proved that every graph with no odd hole or antihole either falls into one of five well-understood classes, or admits a useful decomposition; and Berge's conjecture is a consequence.

The proof is lengthy (150 pages), and this talk will just be a survey of some of the background and ideas involved.