Details

Autor(en) / Beteiligte

• Bianchi, Silvia M.
• Escalante, Mariana S.
• Nasini, Graciela L.
• Wagler, Annegret K.

Titel

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

Ist Teil von

• Discrete Applied Mathematics, 2023-06, Vol.332, p.70-86

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2023

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.