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