TY - JOUR
T1 - The strong perfect graph theorem
AU - Chudnovsky, Maria
AU - Robertson, Neil
AU - Seymour, Paul
AU - Thomas, Robin
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33748570447&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748570447&partnerID=8YFLogxK
U2 - 10.4007/annals.2006.164.51
DO - 10.4007/annals.2006.164.51
M3 - Article
AN - SCOPUS:33748570447
SN - 0003-486X
VL - 164
SP - 51
EP - 229
JO - Annals of Mathematics
JF - Annals of Mathematics
IS - 1
ER -