Evènement pour le groupe GT Graphes et Applications

Date 2012-05-04  14:00-15:00
TitrePerfect matchings in cubic graphs 
RésuméLovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite cubic graphs by Voorhoeve in 1979, and for planar cubic graphs by Chudnovsky and Seymour in 2008. Then several general lower bounds for the number of perfect matchings in cubic bridgeless graphs appeared, and finally, the conjecture has been settled last year. In this talk, a survey on methods used to attain these results is provided.  
LieuSalle 178 
OrateurFrantisek Kardos 
UrlInria Sophia-antipolis 

Aucun document lié à cet événement.

Retour à l'index