← All problems

The Berge graph decomposition conjecture

23 years old · traced to

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∣+∣A2∣≥3|A_1|+|A_2|\geq 3, ∣B∣≥2|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.

References

Status

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.