
In a properly colored (PC) path (see [1]}) or trail (see
[2]}), consecutive edges must have different
colors. Both can be found in linear time by reduction to augmenting paths, and
conversely augmenting paths are a special case of both these problems. The
structural result for PC cycles is Yeo's theorem on cut vertices separating
colors [1]}.

In a rainbow (also called heterochromatic or
multicolored) path, all edges have different colors. Finding a
rainbow path is NP-complete [4]} in the general
case; there is also an algorithm running in \(2^k n^{O(1)}\)  time and polynomial
space for \(k\)  colors and \(n\)  vertices [5]}. Let us also
mention the related subject of rainbow connectivityAn
edge-colored graph is rainbow connected if all pairs of vertices can be
joined by a rainbow path; a common question is coloring the edges of a graph
with a minimum number of colors to make it rainbow connected., that has
been an active area of research (see e.g. the PhD
thesis [6]}) since its introduction in
[7]}.

