The problem
A graph is perfect (chromatic number equals clique number for every induced subgraph) if and only if neither it nor its complement contains an induced odd cycle of length at least five. (Resolved 2002.)
The strong perfect graph theorem
historicHistory & significance
Berge (1960s) conjectured perfection is exactly the absence of odd holes and antiholes; the weak form (complement of perfect is perfect) fell to Lovász in 1972, but the strong form resisted forty years of decomposition attempts. Chudnovsky–Robertson–Seymour–Thomas (announced 2002, published 2006) proved it via the structural decomposition of Berge graphs — a ~150-page argument introducing balanced skew partitions and 2-joins as the central tools. One of the longest single proofs in graph theory, and the capstone of the perfection story.
Connected problems
- related The Four Colour Theorem
More in Graph theory
- same area The Petersen colouring conjecture
- same area The total colouring conjecture
- same area The Goldberg–Seymour conjecture
References
- primaryRead the primary source →
- sourceStrong perfect graph theorem
The resolution (human proof)
Chudnovsky–Robertson–Seymour–Thomas (announced 2002) proved every Berge graph is perfect via structural decomposition (balanced skew partitions, 2-joins) — a ~150-page proof closing a forty-year quest.
Verified by curator — see the API for full claim provenance.