Berge's characterization of minimally imperfect graphs
Berge's characterization of minimally imperfect graphs
Let 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 , and an odd hole is a hole with an odd number of vertices. Let denote the complement of . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.