Evènement pour le groupe GT Graphes et Applications


Date 2015-10-23  14:00-15:00
TitreThe N+-Perfect Graph Conjecture for Claw-Free Graphs 
Résumé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 of STAB(G) 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); we verify it for the well-studied class of claw-free graphs.  
LieuSalle 178 
OrateurAnnegret Wagler 



Aucun document lié à cet événement.

Retour
Retour à l'index