The LS+-perfect graph conjecture

Let GG be a graph. Write STAB(G){\rm STAB}(G) for its stable set polytope and ASTAB(G){\rm ASTAB}^*(G) for the polyhedral relaxation associated with joined a-perfect graphs. A graph is LS+{\rm LS}_+-perfect when LS+(G)=STAB(G){\rm LS}_+(G)={\rm STAB}(G), where LS+(G){\rm LS}_+(G) is the Lovász–Schrijver positive semidefinite relaxation applied to ESTAB(G){\rm ESTAB}(G).

LS+{\rm LS}_+-perfect graph conjecture. A graph GG is LS+{\rm LS}_+-perfect if and only if

STAB(G)=ASTAB(G).{\rm STAB}(G)={\rm ASTAB}^*(G).

Equivalently, the conjecture asserts that LS+{\rm LS}_+-perfect graphs coincide with joined a-perfect graphs, with ASTAB(G){\rm ASTAB}^*(G) serving as the corresponding polyhedral relaxation of STAB(G){\rm STAB}(G).

Sources & referencesView supporting material

Primary source

Silvia Bianchi, Mariana Escalante, Graciela Nasini and Annegret Wagler, “Lovász-Schrijver PSD-operator on Claw-Free Graphs”, arXiv:1612.02670 (2016).

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.