The Strong Perfect Graph Theorem
By M. Chudnovsky, N. Robertson, Paul D. Seymour, R. Thomas. 2002
680 citations recorded by the source corpus.
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, Cornu?ejols and Vuiskovi?c ? 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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/6222834e5307d5c51c234144aee9989e5c4560a8
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- A bound on the chromatic number using the longest odd cycle length (2007, background): “In the following, Lemma 3 follows easily by SPGT [9] and Lemma 4 can be routinely verified.”
- All (k;g)-cages are k-edge-connected (2005, neutral): “was introduced by Berge in 1961, culminating in the proof by Chudnovsky, Robertson, Seymour, and Thomas [2] of the strong perfect graph theorem.”
- There exist graphs with super-exponential Ramsey multiplicity constant (2008, background): “Forbidden subgraph notions have proven fruitful in graph theory; Kuratowski’s Theorem can be rephrased as a statement of which induced subgraphs are forbidden for planar graphs, and the Strong Perfect Graph Theorem [2] characterizes perfect graphs in terms of their forbidden subgraphs.”
- A Combinatorial Approach to Nonlocality and Contextuality (2012, neutral): “3 (Strong perfect graph theorem [28]).”