On 04.06.2009 at 12:20 in S6, there is the following noon lecture:
Perfect matchings in cubic graphs
Lovasz and Plummer conjectured in the 70's that cubic bridgeless graphs have an exponential number of perfect matchings. It has been verified for bipartite cubic graphs by Voorhoeve in 1979 and recently for planar cubic graphs by Chudnovsky and Seymour. In the general case the only known bounds were linear. In this talk, I will explain how to prove a superlinear bound in the general case.
(joint work with F. Kardos and D. Kral')
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010