Skip to Main content Skip to Navigation
New interface
Journal articles

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

Louis Esperet 1, * František Kardoš 2, 3 Daniel Kráľ 4 
* Corresponding author
1 G-SCOP_OC - Optimisation Combinatoire
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 , Laboratoire I3S - 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.
Document type :
Journal articles
Complete list of metadata
Contributor : František Kardoš Connect in order to contact the contributor
Submitted on : Tuesday, November 8, 2011 - 10:41:22 AM
Last modification on : Thursday, August 4, 2022 - 4:52:44 PM
Long-term archiving on: : Thursday, February 9, 2012 - 2:20:52 AM


Files produced by the author(s)



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



Record views


Files downloads