A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
From MaRDI portal
Publication:412270
DOI10.1016/J.EJC.2011.09.027zbMATH Open1239.05149arXiv1002.4739OpenAlexW1994517928WikidataQ57601371 ScholiaQ57601371MaRDI QIDQ412270FDOQ412270
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)
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.
Full work available at URL: https://arxiv.org/abs/1002.4739
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
- Matching theory
- Maximum matching and a polyhedron with 0,1-vertices
- Matching structure and the matching lattice
- Brick decompositions and the matching rank of graphs
- Rank of maximum matchings in a graph
- Perfect matchings in planar cubic graphs
- A new lower bound on the number of perfect matchings in cubic graphs
- Title not available (Why is that?)
- Perfect matchings in claw-free cubic graphs
- Title not available (Why is that?)
- An improved linear bound on the number of perfect matchings in cubic graphs
Cited In (9)
- Perfect matchings in claw-free cubic graphs
- An improved linear bound on the number of perfect matchings in cubic graphs
- A new lower bound on the number of perfect matchings in cubic graphs
- Antiferromagnetic Ising model in triangulations with applications to counting 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
- Cubic bridgeless graphs have more than a linear number of perfect matchings
- 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)
