首页|On the Lovász–Schrijver PSD-operator on graph classes defined by clique cutsets
On the Lovász–Schrijver PSD-operator on graph classes defined by clique cutsets
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2019 Elsevier B.V.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 polytope 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.
Graph classes defined by clique cutsetsLS+-perfect graphsStable set polytope
Wagler A.K.
展开 >
LIMOS (UMR 6158 CNRS) University Clermont Auvergne Clermont-Ferrand
NSTL
Elsevier
