Cycles through \(k\) vertices in bipartite tournaments (Q1330800): Difference between revisions

The authors give a simple proof that every \(k\)-connected bipartite tournament has a cycle through every set of \(k\) vertices. This was conjectured by \textit{R. Häggkvist} and \textit{Y. Manoussakis} [Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica 9, No. 1, 33-38 (1989; Zbl 0681.05036)]. The authors conjecture the existence of a polynomial algorithm to decide the existence of a cycle through \(k\) given vertices (arcs) in a bipartite tournament and to find one if it exists.