Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 24.03.2011 at 12:20 in S1, there is the following noon lecture:

Hamilton cycles in dense vertex-transitive graphs

Honza Hladký

Charles University & University of Warwick

Abstract

A famous conjecture of Lovasz states that every connected vertex-transitive graph contains a Hamilton path. We confirm the conjecture in the case that the graph is dense and sufficiently large. In fact, we show that such graphs contain a Hamilton cycle and moreover we provide a polynomial time algorithm for finding such a cycle. Our proof relies on the Regularity Lemma.

Joint work with D. Christofides and A. Mathe. http://arxiv.org/abs/1008.2193

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010