Lovász-Schrijver PSD-Operator on Some Graph Classes Defined by Clique Cutsets

Abstract : This work is devoted to the study of the Lovász-Schrijver PSD-operator LS+ applied to the edge relaxation ESTAB(G) of the stable set poly-tope STAB(G) of a graph G. In order to characterize the graphs G for which STAB(G) is achieved in one iteration of the LS+-operator, called LS+-perfect graphs, an according conjecture has been recently formulated (LS+-Perfect Graph Conjecture). Here we study two graph classes defined by clique cutsets (pseudothreshold graphs and graphs without certain Truemper configurations). We completely describe the facets of the stable set polytope for such graphs, which enables us to show that one class is a subclass of LS+-perfect graphs, and to verify the LS+-Perfect Graph Conjecture for the other class.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.uca.fr/hal-02017441
Contributor : Annegret Wagler <>
Submitted on : Wednesday, February 13, 2019 - 10:55:08 AM
Last modification on : Monday, January 20, 2020 - 12:14:06 PM
Long-term archiving on: Tuesday, May 14, 2019 - 3:58:59 PM

File

w_isco2018_hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02017441, version 1

Collections

Citation

Annegret K. Wagler. Lovász-Schrijver PSD-Operator on Some Graph Classes Defined by Clique Cutsets. Combinatorial Optimization: ISCO 2018, pp.416-427, 2018. ⟨hal-02017441⟩

Share

Metrics

Record views

27

Files downloads

79