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 - 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 , 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 metadatas

https://hal.inria.fr/hal-00635917
Contributor : František Kardoš <>
Submitted on : Tuesday, November 8, 2011 - 10:41:22 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Thursday, February 9, 2012 - 2:20:52 AM

File

EKK11_.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

440

Files downloads

241