Friday, March 18, 2011 |
|
|
|
Exponentially many perfect matchings in cubic graphs |
|
A well-known conjecture of Lovasz and Plummer asserts that the number
of perfect matchings in 2-edge-connected cubic graph is exponential in
the number of vertices. Voorhoeve has shown in 1979 that the
conjecture holds for bipartite graphs, and Chudnovsky and Seymour have
recently shown that it holds for planar graphs. In general case,
however, the best known lower bound has been until now barely
super-linear. |