Hamiltonian cycles in k ‐partite graphs

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