The strong perfect graph theorem. (English) Zbl 1112.05042

Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin

Ann. Math. (2) 164, No. 1, 51-229 (2006).

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 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). 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 M. Conforti, G. Cornuéjols and 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.

Reviewer: Arthur T. White (Kalamazoo)

MSC:

05C17

Perfect graphs

Keywords:

chromatic number