Paths and cycles in colored graphs

Abstract

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. Several exact and approximation algorithms for finding a path with the fewest colors are provided. The complexity of the exact algorithms and the performance ratio of the approximation algorithms are analyzed. We also pose a problem on the existence of paths and cycles with many different colors.