Given an undirected graph ($V$ vertices, $E$ edges) with maximum vertex degree $< k$ I want to find a vertex coloring using exactly $k$ colors so that no two adjacent vertices have the same color and for each vertex there exists a path starting in it such that no two vertices on this path has the same color and it contains exactly $k$ vertices. Additionaly, I know that in this graph there is at least one cycle of length exactly $k$. Have you got any ideas how to tackle this problem?