Department of
Applied
Mathematics

Perfect matchings in cubic bridgeless graphs

Dan Kral

Abstract

In the 1970's, Lovasz and Plummer conjectured that the number of perfect matchings of every cubic bridgeless is exponential in the number of its vertices. The conjecture has been verified for several classes of cubic bridgeless graphs, in particular, bipartite graphs (Voorhoeve, 1979) and planar graphs (Chudnovsky and Seymour, 2008). We prove the conjecture in full generality.

The talk is based on joint work with Louis Esperet, Frantisek Kardos, Andrew King and Serguei Norine