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