Evènement pour le groupe GT Graphes et Applications


Date 2008-12-19  14:00-15:00
TitreCompter les couplages parfaits dans les graphes cubiques 
RésuméLovasz et Plummer ont conjecturé dans les années 70 que les graphes cubiques 2-arête-connexes ont un nombre exponentiel de couplages parfaits. Cela a été montré pour les graphes bipartis en 1979 par Voorhoeve, et très récemment pour les graphes planaires par Chudnovsky et Seymour. Dans le cas général les meilleures bornes connues sont linéaires : Edmonds, Lovász, et Pulleyblank, et indépendamment Naddef, ont prouvé en 1982 que la dimension du polytope des couplages parfaits d'un graphe cubique 2-arête-connexe a n sommets est au moins n/4+1 (ce qui implique directement qu'ils ont au moins n/4+2 couplages parfaits). En utilisant un résultat récent de Král', Sereni, et Stiebitz, nous montrons que tout graphe cubique 2-arête-connexe a n sommets a au moins 3n/4-10 couplages parfaits. Notre preuve est inductive et repose largement sur la "brick and brace decomposition" introduite par Edmonds, Lovász, et Pulleyblank en 1982. (travail en commun avec Daniel Král, Petr ¦koda, et Riste ¦krekovski)  
Lieusalle 075 
OrateurLouis Esperet 



Aucun document lié à cet événement.

Retour
Retour à l'index