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.
Full Article