Perfect Matchings in Claw-free Cubic Graphs

Sang-il Oum (엄상일)

Department of Mathematical Sciences, KAIST

Department of Mathematical Sciences, KAIST

2009/10/9 Friday 4PM-5PM

Lovász 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/18} perfect matchings, thus verifying the conjecture for claw-free graphs.

Tags: 엄상일