Paths and cycles in colored graphs

Let G be an (edge-)colored graph. A path (cycle) is called monochromatic if all of its edges have the same color, and is called heterochromatic. if all of its edges have different colors. In this paper, some sufficient conditions for the existence of (long) monochromatic paths and cycles, and those for the existences of long heterochromatic paths and cycles are obtained. It is proved that the problem of finding a path (cycle) with as few different colors as possible in a colored graph is NP-hard. Exact and approximation algorithms for finding a path with the fewest colors are provided. The complexity of the exact algorithm and the performance ratio of the approximation algorithm are analyzed. We also pose a problem on the existence of paths and cycles with many different colors.