The Berge graph decomposition conjecture

Let GG 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 A,B,C,DA,B,C,D with all possible edges between AA and BB and no edges between CC and DD. A homogeneous pair is a partition of V(G)V(G) into A1,A2,BA_1,A_2,B with A1+A23|A_1|+|A_2|\geq 3, B2|B|\geq 2, and every vertex of BB adjacent to a vertex of AiA_i adjacent to all vertices of AiA_i, for i=1,2i=1,2. A 2-join is the decomposition notion used in the source. Decomposition conjecture. Every Berge graph GG is basic or has a skew partition or a homogeneous pair, or GG or Gˉ\bar G 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

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.