Berge's characterization of minimally imperfect graphs

Let GG be a finite simple graph. A minimally imperfect graph is a graph that is not perfect but whose proper induced subgraphs are all perfect. A hole is a chordless cycle of length at least 44, and an odd hole is a hole with an odd number of vertices. Let Gˉ\bar G denote the complement of GG. Berge's conjecture. The only minimally imperfect graphs are the odd holes and their complements.

This is an equivalent formulation of the Strong Perfect Graph Conjecture. It was proved by Lovász's Perfect Graph Theorem together with the later proof of the Strong Perfect Graph Conjecture by Chudnovsky, Robertson, Seymour and Thomas.

Sources & referencesView supporting material

Primary source

Gérard Cornuéjols, “The strong perfect graph conjecture”, arXiv:math/0304464 (2003).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.