Given an undirected graph with bounded degree (degree smaller than $k$ for each vertex) I want to find a 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 containing exactly $k$ vertices, each of different color. 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?