TY - JOUR

T1 - The strong perfect graph theorem

AU - Chudnovsky, Maria

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

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

VL - 164

SP - 51

EP - 229

JO - Annals of Mathematics

JF - Annals of Mathematics

SN - 0003-486X

IS - 1

ER -