The Berge graph decomposition conjecture
Let be a finite simple graph. A Berge graph is a graph containing neither an odd hole nor the complement of an odd hole. A graph is basic if it belongs to one of the four classes consisting of bipartite graphs, line graphs of bipartite graphs, or their complements. A skew partition is a partition of the vertices into four nonempty sets with all possible edges between and and no edges between and . A homogeneous pair is a partition of into with , , and every vertex of adjacent to a vertex of adjacent to all vertices of , for . A 2-join is the decomposition notion used in the source. Decomposition conjecture. Every Berge graph is basic or has a skew partition or a homogeneous pair, or or has a 2-join.
The source attributes this structural conjecture to Conforti, Cornuéjols, Robertson, Seymour, Thomas and Vušković (2001), and says that it implies 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/2006/164-1/p02
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
No solutions have been posted yet.