An improved linear bound on the number of perfect matchings in cubic graphs

DOI10.1016/J.EJC.2009.11.008zbMath1218.05127arXiv0901.3894OpenAlexW2122238195WikidataQ57601406 ScholiaQ57601406MaRDI QIDQ976154

Louis Esperet, Daniel Král', Riste Škrekovski, Petr Škoda

Publication date: 17 June 2010

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

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

zbMATH Keywords

perfect matching polytope

Mathematics Subject Classification ID

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

Related Items (3)

A superlinear bound on the number of perfect matchings in cubic bridgeless graphs ⋮ Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings ⋮ Exponentially many perfect matchings in cubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Brick decompositions and the matching rank of graphs
• Matching theory
• Matching structure and the matching lattice
• Counting 1-factors in regular bipartite graphs
• Perfect matchings in planar cubic graphs
• Graphs with independent perfect matchings
• A New Lower Bound on the Number of Perfect Matchings in Cubic Graphs
• Rank of maximum matchings in a graph
• Maximum matching and a polyhedron with 0,1-vertices
• Concerning a Conjecture of Marshall Hall
• On Lower Bounds for Permanents of (0, 1) Matrices
• On the Permanent of a Certain Class of (0, 1)-Matrices

This page was built for publication: An improved linear bound on the number of perfect matchings in cubic graphs