Clique–Stable Set separation conjecture for graphs

Let GG be a graph on nn vertices. A clique–stable set separator is a family of cuts such that every disjoint clique and stable set of GG are separated by one of the cuts. Clique–Stable Set separation conjecture. There is a polynomial QQ such that every graph GG on nn vertices has a CS-separator of size at most

Q(n).Q(n).

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

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.