Clique–Stable Set separation conjecture for HH-free graphs

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.

Sources & referencesView supporting material

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.