Perfect Matchings in Claw-free Cubic Graphs

Sang-il Oum
Arxiv ID: 0906.2261Last updated: 10/5/2022
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.

PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.

Related papers

Commercial Disclosure
© 2023 Paper Studio™. All Rights Reserved.