Cycles in Regular Multipartite Tournaments

Abstract

We study balanced cycles in regular multipartite tournaments. A cycle in a $c$-partite tournament is $k$-balanced if it contains exactly $k$ vertices from each partite class. We prove that there exists an absolute integer $r_0$ such that every regular $c$-partite tournament with each partite class size of $r\ge r_0$ contains a $k$-balanced cycle for every $1\le k\le r$ when $c=3$ or $c\ge 5$, and for every $2\le k\le r$ when $c=4$. In particular, our result confirms three conjectures of Volkmann and Winzen for large regular multipartite tournaments. We also confirm Yeo's conjecture on the existence of $(p,q)$-cycle factors for large regular $c$-partite tournaments $G$ with $c\ge 4$, where a $(p,q)$-cycle factor is a pair of vertex-disjoint cycles of lengths $p$ and $q$ spanning $G$.

arXiv comment16pages