Clique–Stable Set separation conjecture for HH-free graphs

About 13 years old · traced to

Let HH be a fixed graph, and let an HH-free graph be a graph with no induced subgraph isomorphic to HH. A CS-separator is a family of cuts separating every disjoint clique from every stable set. Clique–Stable Set separation conjecture for HH-free graphs. The Clique–Stable Set separation conjecture is true on HH-free graphs.

The source presents this as a proposed restriction of the general separation conjecture, motivated by evidence for perfect graphs and other graph classes. No resolution is given in the supplied text.

References

Primary source

Nicolas Bousquet, Aurélie Lagoutte and Stéphan Thomassé, “Clique versus Independent Set”, arXiv:1301.2474 (2014).

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.