Hamiltonian cycles in k-partite graphs

Chen et al determined the minimum degree threshold for which a balanced -partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary -partite graphs in that all parts have at most vertices (a necessary condition). To do this, we first prove a general result that both simplifies the process of checking whether a graph is a robust expander and gives useful structural information in the case when is not a robust expander. Then we use this result to prove that any -partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.