Department of
Applied
Mathematics

Perfect matchings in cubic graphs

Louis Esperet

Abstract

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')