Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs

BIANCHI, SILVIA M.; ESCALANTE, MARIANA S.; NASINI, GRACIELA L.; WAGLER, ANNEGRET K.

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Año: 2023 vol. 332 p. 70 - 86

0166-218X

The subject of this work is the study of LS+-perfect graphs defined as those graphs G for which the stable set polytope STAB(G) is achieved in one iteration of Lovász–Schrijver PSD-operator LS+, applied to its edge relaxation ESTAB(G). The recently formulated LS+-Perfect Graph Conjecture aims at a characterization of this family of graphs, through the structure of the facet defining inequalities of the stable set polytope. The main contribution of this work is to verify it for the well-studied class of claw-free graphs.