The strong perfect graph theorem
| dc.creator | Chudnovsky, Maria | |
| dc.creator | Robertson, Neil | |
| dc.creator | Seymour, Paul | |
| dc.creator | Thomas, Robin | |
| dc.date | 2002-12-04 | |
| dc.date.accessioned | 2026-07-07T04:53:32Z | |
| dc.date.available | 2026-07-07T04:53:32Z | |
| dc.description | 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 5 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, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures. | |
| dc.description | 150 pages | |
| dc.identifier | https://arxiv.org/abs/math/0212070 | |
| dc.identifier | http://arxiv.org/abs/math/0212070 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/65890 | |
| dc.subject | Combinatorics | |
| dc.title | The strong perfect graph theorem | |
| dc.type | text |