Lovász-Schrijver PSD-operator on Claw-Free Graphs
Preprint
Abstract
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\'asz-Schrijver PSD-operator $\LS_+$, applied to its edge relaxation $\estab(G)$. In particular, we look for a polyhedral relaxation of $\stab(G)$ that coincides with $\LS_+(\estab(G))$ and $\stab(G)$ if and only if $G$ is $\LS_+$-perfect. An according conjecture has been recently formulated ($\LS_+$-Perfect Graph Conjecture); here we verify it for the well-studied class of claw-free graphs.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- The stable set polytope of quasi-line graphsCombinatorica, 2008
- Characterizing and bounding the imperfection ratio for some classes of graphsMathematical Programming, 2007
- Almost all webs are not rank-perfectMathematical Programming, 2005
- Antiwebs are rank-perfect4OR, 2004
- On non-rank facets of the stable set polytope of claw-free graphs and circulant graphsMathematical Methods of Operations Research, 2004
- The stable set problem and the lift-and-project ranks of graphsMathematical Programming, 2003
- The Rank Facets of the Stable Set Polytope for Claw-Free GraphsJournal of Combinatorial Theory, Series B, 1997
- Applying Lehman's theorems to packing problemsMathematical Programming, 1995
- Near-perfect matricesMathematical Programming, 1994
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981