A superlinear bound on the number of perfect matchings in cubic bridgeless graphs

Louis Esperet 1, * František Kardoš 2, 3 Daniel Kráľ 4
* Auteur correspondant
1 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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 graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear bound in the general case.
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2012, 33 (5), pp.767-798. 〈10.1016/j.ejc.2011.09.027〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00635917
Contributeur : František Kardoš <>
Soumis le : mardi 8 novembre 2011 - 10:41:22
Dernière modification le : mercredi 29 juillet 2015 - 01:18:13
Document(s) archivé(s) le : jeudi 9 février 2012 - 02:20:52

Fichier

EKK11_.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Louis Esperet, František Kardoš, Daniel Kráľ. A superlinear bound on the number of perfect matchings in cubic bridgeless graphs. European Journal of Combinatorics, Elsevier, 2012, 33 (5), pp.767-798. 〈10.1016/j.ejc.2011.09.027〉. 〈hal-00635917〉

Partager

Métriques

Consultations de
la notice

208

Téléchargements du document

112