The strong perfect graph theorem (Q855256): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q29028413, #quickstatements; #temporary_batch_1706974296281 |
Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1973199140 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0212070 / rank | |||
Normal rank |
Latest revision as of 18:18, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The strong perfect graph theorem |
scientific article |
Statements
The strong perfect graph theorem (English)
0 references
4 January 2007
0 references
A graph \(G\) is perfect if, for every induced subgraph \(H\) of \(G\), the chromatic number of \(H\) equals the order of the largest complete subgraph of \(H\). A graph \(G\) is Berge if no induced subgraph of \(G\) is either an odd cycle of length five or more or the complement of such a graph. The study of these graphs was begun by \textit{C. Berge} in 1961 [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114 (1961)], in connection with a problem in information theory (the ``Shannon capacity'' of a graph lies between the clique number and the chromatic number, so for a perfect graph it equals both). Berge made two famous conjectures: (1) The complement of a perfect graph is perfect; and (2) A graph is perfect if and only if it is Berge. Since (2) implies (1), these are known as the strong perfect graph conjecture (2) and the weak perfect graph conjecture (1). \textit{L. Lovász} proved (1) in 1972 [J. Comb. Theory, Ser. B 13, 95--98 (1972; Zbl 0241.05107)]. Much attention has been given to (2) in the intervening four decades, and a proof is given in the present paper. A conjecture even stronger than (2) was made by \textit{M. Conforti}, \textit{G. Cornuéjols} and \textit{K. Vuskovic} in 2004 [J. Comb. Theory, Ser. B 90, No. 2, 257--307 (2004; Zbl 1033.05047)], namely 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 (2) cannot have either of these properties). In the present paper, the authors prove this conjecture also.
0 references
chromatic number
0 references