Andrew King, Proving the Lovász-Plummer Conjecture

Proving the Lovász-Plummer Conjecture
Andrew King
Department of Mathematics and Computer Science, Simon Fraser University, Vancouver, Victoria, Canada
2012/02/08 Wed 4PM-5PM
In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings. This was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds’ characterization of the perfect matching polytope.
(Joint work with Louis Esperet, František Kardoš, Daniel Král’, and Sergey Norin.)

Tags:

This entry was posted on Saturday, January 28th, 2012 at 4:47 pm and is filed under 2012, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.