On 24.03.2011 at 12:20 in S1, there is the following noon lecture:
Hamilton cycles in dense vertex-transitive graphs
Charles University & University of Warwick
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
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010