A characterization of rich \(c\)-partite \((c \geq 7)\) tournaments without \((c + 2)\)-cycles
In this paper, the authors focus on a characterization problem concerning a special class of \(c\)-partite tournaments: orientations of complete \(c\)-partite graphs.\N\NA digraph \(D\) is strong if, for every pair \(x, y\) of distinct vertices in \(D\), there exists a path from \(x\) to \(y\) and a path from \(y\) to \(x\).\N\NA \(c\)-partite tournament is said to be rich if it is strong, with each partite set containing \(n\geq 2\) vertices (for \(n=1\), we get tournaments on \(c\) vertices). For \(c\geq 5\), the family of all rich \(c\)-partite tournaments is denote by \(\mathcal{D}\). A \(q\)-cycle is a cycle with \(q\) arcs. \N\NIn [J. Lond. Math. Soc., II. Ser. 14, 277--282 (1976; Zbl 0344.05124)], \textit{J. A. Bondy} asked whether every multipartite tournament of \(\mathcal{D}\) contains a \((c + 1)\)-cycle. This was answered in the negative by \textit{G. Gutin} [Vestsi Acad. Navuk BSSR Ser. Fiz.-Mat., 5, 105--106 (1984; Zbl 0556.05033)], and later \textit{Y. Guo} and \textit{L. Volkmann} [J. Combin. Theory Ser. B, 66, 140--145 (1996; Zbl 0837.05067)] provided a complete characterization of tournaments of \(\mathcal{D}\) that have no \((c+1)\)-cycles.\N\NThe previous problem can be generalized, so looking for a characterization of rich \(c\)-partite tournaments without \((c + k)\)-cycles for some \(k\geq 2\).\N\NThe authors solve the problem for \(c\geq 8\) and \(k=2\).\par\N\NThe condition \(c\geq 8\) might be not sharp, so the characterization of rich \(c\)-partite tournaments without \((c + 2)\)-cycles, and \(5\leq c\leq 7\) remains an open problem
scientific article; zbMATH DE number 7908415