The Berge graph decomposition conjecture
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. The supplied text gives no resolution status.
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.