The strong perfect graph theorem (Q855256): Difference between revisions

A graph \(G\) is perfect if, for every induced subgraph \(H\) of \(G\), the chromatic number of \(H\) equals the order of the largest complete subgraph of \(H\). A graph \(G\) is Berge if no induced subgraph of \(G\) is either an odd cycle of length five or more or the complement of such a graph. The study of these graphs was begun by \textit{C. Berge} in 1961 [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114 (1961)], in connection with a problem in information theory (the ``Shannon capacity'' of a graph lies between the clique number and the chromatic number, so for a perfect graph it equals both). Berge made two famous conjectures: (1) The complement of a perfect graph is perfect; and (2) A graph is perfect if and only if it is Berge. Since (2) implies (1), these are known as the strong perfect graph conjecture (2) and the weak perfect graph conjecture (1). \textit{L. Lovász} proved (1) in 1972 [J. Comb. Theory, Ser. B 13, 95--98 (1972; Zbl 0241.05107)]. Much attention has been given to (2) in the intervening four decades, and a proof is given in the present paper. A conjecture even stronger than (2) was made by \textit{M. Conforti}, \textit{G. Cornuéjols} and \textit{K. Vuskovic} in 2004 [J. Comb. Theory, Ser. B 90, No. 2, 257--307 (2004; Zbl 1033.05047)], namely 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 (2) cannot have either of these properties). In the present paper, the authors prove this conjecture also.