Given a graph $D=(V(D),A(D))$ and a coloring of $D$, not necessarily a proper coloring of either the arcs or the vertices of $D$, we consider the complexity of finding a path of $D$ from a given vertex $s$ to another given vertex $t$ with as few different colors as possible, and of finding one with as many different colors as possible. We show that the first problem is polynomial-time solvable, and that the second problem is NP-hard.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||16|
|Publication status||Published - 2000|
|Name||Memorandum Faculteit TW|
|Publisher||University of Twente|
Li, X., Li, X., Zhang, S., & Broersma, H. J. (2000). Directed paths with few or many colors in colored directed graphs. (Memorandum Faculteit TW; No. 1543). Enschede: University of Twente, Department of Applied Mathematics.