Strong perfect graph theorem

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, the strong perfect graph theorem is a <a href="/facts/Forbidden_graph_characterization/50Kex6JU">forbidden graph characterization</a> of the <a href="/facts/Perfect_graph/wcPdhjG9">perfect graphs</a> as being exactly the graphs that have neither odd holes (odd-length <a href="/facts/Induced_cycle/zfcIx9Sw">induced cycles</a> of length at least 5) nor odd antiholes (complements of odd holes). It was <a href="/facts/Conjecture/oPWUb7SF">conjectured</a> by <a href="/facts/Claude_Berge/VPsApqnu">Claude Berge</a> in 1961. A <a href="/facts/Mathematical_proof/7ECDrU80">proof</a> by <a href="/facts/Maria_Chudnovsky/MrP7qyTT">Maria Chudnovsky</a>, <a href="/facts/Neil_Robertson_(mathematician)/nC5FXjur">Neil Robertson</a>, <a href="/facts/Paul_Seymour_(mathematician)/AJp2GgAC">Paul Seymour</a>, and <a href="/facts/Robin_Thomas_(mathematician)/A3fS9arb">Robin Thomas</a> was announced in 2002 and published by them in 2006.
</p><p>The proof of the strong perfect graph theorem won for its authors a $10,000 prize offered by <a href="/facts/G%C3%A9rard_Cornu%C3%A9jols/YgzLaU7m">Gérard Cornuéjols</a> of Carnegie Mellon University and the 2009 <a href="/facts/Fulkerson_Prize/aUrCCpgK">Fulkerson Prize</a>.
</p>

Strong perfect graph theorem open-in-new

Strong perfect graph theorem