Clique–Stable Set separation conjecture for graphs
Clique–Stable Set separation conjecture for graphs
Let be a graph on vertices. A clique–stable set separator is a family of cuts such that every disjoint clique and stable set of are separated by one of the cuts. Clique–Stable Set separation conjecture. There is a polynomial such that every graph on vertices has a CS-separator of size at most
The source says that this positive formulation is generally believed to be false, while establishing such separators for several graph classes. Its general status is not resolved 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.