Lovasz-Schrijver PSD-operator on Claw-Free Graphs.

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR; WAGLER, ANNEGRET

Vietri sul Mare (Salerno)

Simposio; 4th International Symposium on Combinatorial Optimization (ISCO 2016); 2016

ISCO

The subject of this work is the study of the Lov´asz-SchrijverPSD-operator LS+ applied to the edge relaxation ESTAB(G) of the stableset polytope STAB(G) of a graph G.We are interested in the problemof characterizing the graphs G for which STAB(G) is achieved in one iterationof the LS+-operator, called LS+-perfect graphs, and to find an appropriatepolyhedral relaxation of STAB(G) that coincides with LS+(G)and STAB(G) if and only if G is LS+-perfect. An according conjecturehas been recently formulated (LS+-Perfect Graph Conjecture); here weverify it for the well-studied class of claw-free graphs.