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

DOI10.1016/J.EJC.2011.09.027MaRDI QIDQ412270zbMATH OpenOpenAlexWikidataFDO

Authors L. Esperet, František Kardoš, Daniel Král'

Publication date 4 May 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.4739

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Lovasz 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.

Recommendations

• An improved linear bound on the number of perfect matchings in cubic graphs
• Cubic bridgeless graphs have more than a linear number of perfect matchings
• A new lower bound on the number of perfect matchings in cubic graphs
• On maximum matchings in cubic graphs with a bounded number of bridge-covering paths
• On the maximum fraction of edges covered by \(t\) perfect matchings in a cubic bridgeless graph
• Exponentially many perfect matchings in cubic graphs
• Non-intersecting perfect matchings in cubic graphs (Extended abstract)
• Perfect matchings with restricted intersection in cubic graphs
• Connected cubic graphs with the maximum number of perfect matchings
• On the expected number of perfect matchings in cubic planar graphs

Cites work

• scientific article; zbMATH DE number 3621721 (Why is no real title available?)
• scientific article; zbMATH DE number 3390835 (Why is no real title available?)
• A new lower bound on the number of perfect matchings in cubic graphs
• An improved linear bound on the number of perfect matchings in cubic graphs
• Brick decompositions and the matching rank of graphs
• Matching structure and the matching lattice
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• Perfect matchings in claw-free cubic graphs
• Perfect matchings in planar cubic graphs
• Rank of maximum matchings in a graph

Cited in

(9)

• Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings
• A new lower bound on the number of perfect matchings in cubic graphs
• Perfect matchings in claw-free cubic graphs
• An improved linear bound on the number of perfect matchings in cubic graphs
• Cubic bridgeless graphs have more than a linear number of perfect matchings
• A bound on the number of perfect matchings in Klee-graphs
• On the expected number of perfect matchings in cubic planar graphs
• Perfect matchings in planar cubic graphs
• Counting perfect matchings in the geometric dual

This page was built for publication: A superlinear bound on the number of perfect matchings in cubic bridgeless graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412270)