Strong perfect graph theorem
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles) nor odd antiholes (complements of odd holes). It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006. The proof of the strong perfect graph theorem won for its authors a $10,000 prize offered by Gérard Cornuéjols of Carnegie Mellon University and the 2009 Fulkerson Prize.
Wikipage redirect
primaryTopic
Strong perfect graph theorem
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles) nor odd antiholes (complements of odd holes). It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006. The proof of the strong perfect graph theorem won for its authors a $10,000 prize offered by Gérard Cornuéjols of Carnegie Mellon University and the 2009 Fulkerson Prize.
has abstract
In graph theory, the strong pe ...... and the 2009 Fulkerson Prize.
@en
Link from a Wikipage to an external page
Wikipage page ID
Wikipage revision ID
702,518,729
title
Strong Perfect Graph Theorem
urlname
StrongPerfectGraphTheorem
hypernym
comment
In graph theory, the strong pe ...... and the 2009 Fulkerson Prize.
@en
label
Strong perfect graph theorem
@en