The strong perfect graph theorem

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticlepeer-review

604 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)51-229
Number of pages179
JournalAnnals of Mathematics
Volume164
Issue number1
DOIs
StatePublished - 2006

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'The strong perfect graph theorem'. Together they form a unique fingerprint.

Cite this