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

  1. S. V. N. Vishwanathan
  2. Jacob Fox
  3. Christopher Morris
  4. Petra Mutzel

In Discrete Mathematics and Combinatorics

  1. S. V. N. Vishwanathan
  2. Christopher Morris

Citations in the corpus