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

Benkouar, A.; Manoussakis, Y.; Saad, R.

J. Comb. Math. Comb. Comput. 16, 199-207 (1994).

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)

MSC:

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

Keywords:

edge-colored graphs; color; alternating cycle; bipartite tournament; algorithm

Citations:

Zbl 0715.05042