The strong perfect graph theorem

Abstract

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.

Authors

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