| 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) |