The strong perfect graph theorem

• 成果类型: Article
• 署名作者: Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2006.164.51
• 发表日期: 2006
• 页码: 51-229
• 关键词: minimal imperfect graphs; DECOMPOSITION; PROPERTY

摘要

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 five 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 admits one of a few kinds of separation (designed so that a minimum counterexample to Berge's conjecture cannot have either of these properties). In this paper we prove both of these conjectures.