The full-support facet conjecture for -perfect graphs
The full-support facet conjecture for -perfect graphs
Let denote the Lovász–Schrijver positive semidefinite relaxation of the stable set polytope. A graph is -perfect when , and a facet is full-support when its defining inequality involves every vertex of . The full-support facet conjecture. If a graph is -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 -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
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.