Strong perfect graph theorem
id:
strong-perfect-graph-theorem-166-16344443
title:
Strong perfect graph theorem
text:
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 nor odd antiholes. 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 a
brand slug:
wiki
category slug:
encyclopedia
description:
Perfect graphs have neither odd holes nor odd antiholes
original url:
https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem
date created:
2004-06-22T19:30:29Z
date modified:
2024-08-30T00:30:49Z
main entity:
{"identifier":"Q16680059","url":"https://www.wikidata.org/entity/Q16680059"}
image:
fields total:
13
integrity:
15