The strong perfect graph theorem


A graph $G$ is perfect if for every induced subgraph $H$, the chromatic number of $H$ equals the size of the largest complete subgraph of $H$, and $G$ is Berge if no induced subgraph of $G$ is an odd cycle of length at least five or the complement of one.

The “strong perfect graph conjecture” (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuéjols and Vušković — that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge’s conjecture cannot have either of these properties).

In this paper we prove both of these conjectures.


Maria Chudnovsky

Department of Mathematics
Columbia University
New York, NY 10027
United States

Neil Robertson

Department of Mathematics
The Ohio State University
Columbus, OH 43210
United States

Paul Seymour

Department of Mathematics
Princeton University
Princeton, NJ 08544
United States

Robin Thomas

School of Mathematics
Georgia Institute of Technology
Atlanta, GA 30332
United States