arXiv Analytics

Sign in

arXiv:0901.3894 [math.CO]AbstractReferencesReviewsResources

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

Louis Esperet, Daniel Kral, Petr Skoda, Riste Skrekovski

Published 2009-01-25Version 1

We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.

Categories: math.CO
Subjects: 05C15
Related articles: Most relevant | Search more
arXiv:1301.6926 [math.CO] (Published 2013-01-29, updated 2013-11-15)
On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings
arXiv:2004.06788 [math.CO] (Published 2020-04-14)
Reflexive coloring complexes for 3-edge-colorings of cubic graphs
arXiv:1009.2446 [math.CO] (Published 2010-09-13, updated 2010-09-29)
Three-Colorings of Cubic Graphs and Tensor Operators

Links

Toolbox