The strong perfect graph theorem gives a forbidden-subgraph characterization of perfect graphs, stating that a graph is perfect precisely when it contains neither an odd hole, an induced cycle of odd length five or more, nor an odd antihole, the complement of such a cycle. Claude Berge conjectured the result in 1961, and Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas announced a proof in 2002, published in 2006, earning a ten thousand dollar prize offered by Gerard Cornuejols at Carnegie Mellon University and the 2009 Fulkerson Prize; Berge had already observed that odd holes and odd antiholes cannot appear in a perfect graph, since both have a clique number of two but a chromatic number of three. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Strong perfect graph theorem (Wikipedia)
Sources
1. Strong perfect graph theorem (Wikipedia)
- A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 ... until its proof in 2002, when it was renamed the strong perfect graph theorem
In Branch: Graph Theory, Lead sentence
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.