Paul Seymour

Department of Mathematics
Princeton University

October 2, 4:15pm


Claude Berge proposed the conjecture in 1961 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.  (A "hole"
means an induced subgraph which is a cycle of length >= 4, and an
"antihole" is the same in the complement graph.) This has become one of
the most well-known and popular open problems in graph theory.  Most
attempts on it have been based on linear programming methods, studying the
properties of a minimal counterexample; they go a long way, but appear
eventually to get stuck.  Recently, however, a new approach was initiated
by Conforti and Cornuejols, an attempt to actually find explicit
constructions for all the graphs not containing odd holes or antiholes,
and checking directly that they satisfy Berge's conjecture.  I am happy to
report that this works. In joint work with Maria Chudnovsky, Neil
Robertson and Robin Thomas, we have been able to carry out the
Conforti-Cornuejols program, and thereby prove Berge's conjecture.

Return to Applied Math Colloquium home page