Alternating cycles through fixed vertices in edge-colored graphs. (English) Zbl 0813.05042

Alternating cycles (i.e. cycles such that no consecutive edges have the same color) are of interest in combinatorics. This paper proves that deciding if there exists an alternating cycle through two fixed vertices in an edge-colored complete graph is NP-hard. It also establishes a necessary and sufficient condition for the existence of an alternating cycle containing a vertex in a \(k\)-edge-colored complete graph \(K^ c_ n\). The authors give an \(O(n^ 2)\) algorithm for finding a cycle through two given vertices in a bipartite tournament of order \(n\). This improves an \(O(n^ 3)\) algorithm recently published by Y. Manoussakis and Z. Tuza [SIAM J. Discrete Math. 3, No. 4, 537-543 (1990; Zbl 0715.05042)].
Reviewer: J.Pallo (Dijon)


05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science


Zbl 0715.05042