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.
References
Status
- Solved: Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The Strong Perfect Graph Theorem (Annals of Mathematics, 2006) https://annals.math.princeton.edu/wp-content/uploads/annals-v164-n1-p02.pdf
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.