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

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

2010-02-25

arxiv.org/abs/1002.4739v2

Mathematics

Combinatorics

54 pages v2: a short (missing) proof of Lemma 10 was added

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A superlinear bound on the number of perfect matchings in cubic bridgeless graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A superlinear bound on the number of perfect matchings in cubic bridgeless graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A superlinear bound on the number of perfect matchings in cubic bridgeless graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-379746