Date: February, 23rd, 11h30
Place: Room Rotule NO8 – ULB Bruxelles
Abstract: The subject of this talk is the study of the Lovasz-Schrijver PSD-operator N+ applied to the edge relaxation ESTAB(G) of the stable set polytope STAB(G) of a graph. We are particularly interested in the problem of characterizing the graphs G for which N+(G) := N+(ESTAB(G)) equals STAB(G), called N+-perfect graphs, and to find an appropriate polyhedral relaxation that coincides with N+(G) and STAB(G) if and only if G is N+-perfect. An according conjecture has been recently formulated (N+-Perfect Graph Conjecture); here we verify it for the well-studied class of claw-free graphs.
This is a brand-new result (we plan to submit the paper to IPCO 2016).
