HAMILTONIAN PROBLEMS IN EDGE-COLORED COMPLETE GRAPHS AND EULERIAN CYCLES IN EDGE-COLORED GRAPHS - SOME COMPLEXITY RESULTS

In an edge-colored, we say that a path (cycle) is alternating if it ha s length at least 2 (3) and if any 2 adjacent edges of this path (cycl e) have different colors. We give efficient algorithms for finding alt ernating factors with a minimum number of cycles and then, by using th is result, we obtain polynomial algorithms for finding alternating Ham iltonian cycles and paths in 2-edge-colored complete graphs. We then s how that some extensions of these results to k-edge-colored complete g raphs, k greater than or equal to 3, are NP-complete, related problems are proposed. Finally, we give a polynomial characterization of the e xistence of alternating Eulerian cycles in edge-colored graphs. Our pr oof is algorithmic and uses a procedure that finds a perfect matching in a complete k-partite graph.