Lovász-Schrijver PSD-operator on Claw-Free Graphs

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

LECTURE NOTES IN COMPUTER SCIENCE

springer

Lugar: Berlin; Año: 2017 vol. 9849 p. 59 - 70

0302-9743

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 particularly interested in the problem of characterizing the graphsG for which STAB(G) is achieved in one iteration of the N+-operator,called N+-perfect graphs, and to find an appropriate polyhedral relaxationof STAB(G) that coincides with N+(G) and STAB(G) if and only ifG is N+-perfect. An according conjecture has been recently formulated(N+-Perfect Graph Conjecture); here we verify it for the well-studiedclass of claw-free graphs.