Counterexamples to a Conjecture of Wang Concerning Regular 3-partite Tournaments

Abstract

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament $D$ is contained in directed cycles of all lengths $3,6,9,\dots ,|V(D)|$.

In this paper, we show that this conjecture is completely false. Namely, for each integer $t$ with $3\le t\le |V(D)|$, we present an infinite family of regular 3-partite tournaments $D$ such that there exists an arc in $D$ which is not contained in a directed cycle of length $t$.