Perfect Matchings in Claw-free Cubic Graphs

Abstract

Lovasz and Plummer conjectured that there exists a fixed positive constant c such that every cubic n-vertex graph with no cutedge has at least 2^(cn) perfect matchings. Their conjecture has been verified for bipartite graphs by Voorhoeve and planar graphs by Chudnovsky and Seymour. We prove that every claw-free cubic n-vertex graph with no cutedge has more than 2^(n/12) perfect matchings, thus verifying the conjecture for claw-free graphs.

6 pages, 2 figures

References in corpus (1)

• Exponentially many perfect matchings in cubic graphs

Cited by in corpus (6)

• Normal 6-edge-colorings of some bridgeless cubic graphs
• A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
• On Sylvester Colorings of Cubic Graphs
• A note on 2--bisections of claw--free cubic graphs
• Claw-free cubic graphs are (1, 1, 1, 3)-packing edge-colorable
• Graphs, Disjoint Matchings and Some Inequalities