The full-support facet conjecture for LS+{\operatorname{LS}}_+-perfect graphs

Let LS+(G){\operatorname{LS}}_+(G) denote the Lovász–Schrijver positive semidefinite relaxation of the stable set polytope. A graph is LS+{\operatorname{LS}}_+-perfect when LS+(G)=STAB(G){\operatorname{LS}}_+(G)=\operatorname{STAB}(G), and a facet is full-support when its defining inequality involves every vertex of GG. The full-support facet conjecture. If a graph is LS+{\operatorname{LS}}_+-perfect and its stable set polytope has a full-support facet-defining inequality, then the graph is near-bipartite. This is presented as an equivalent formulation of the paper's open characterization problem for LS+{\operatorname{LS}}_+-perfect graphs.

Sources & referencesView supporting material

Primary source

S. Bianchi, M. Escalante, G. Nasini and L. Tunçel, “Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs”, arXiv:1411.2069 (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.