ALTERNATING PATHS IN EDGE-COLORED COMPLETE GRAPHS

In an edge-colored graph, we say that a path is alternating if it has at least three vertices and any two adjacent edges have different colo rs. Deciding whether or not there exist two disjoint alternating paths between two vertices in edge-colored graphs is NP-complete. In this w ork, we study the existence of alternating paths between vertices by r estricting ourselves to the case of edge-colored complete graphs. We f irst solve the ''vertex-disjoint'' version of this problem and related questions for edge-colored complete graphs. We next give efficient al gorithms for finding a fixed number of pairwise vertex- or edge-disjoi nt paths each of which has given extremities. Related problems are pro posed.