ABSTRACT


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 wellknown 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 ConfortiCornuejols program, and thereby prove Berge's conjecture. Return to Applied Math Colloquium home page 