Paths and cycles in colored graphs. (English) Zbl 1061.05030

Authors’ abstract: Let \(G\) be an (edge-)colored graph. A path (cycle) is called monochromatic if all its edges have the same color, and is called heterochromatic if all its edges have different colors. In this paper, some sufficient conditions for the existence of (long) monochromatic paths and cycles, and those for the existence 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.


05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science