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?
The OP is asking for something which has already been proved to exist in
Saieed Akbari, Vahid Liaghat, Afshin Nikzad: Colorful Paths in Vertex Coloring of Graphs, The electronic journal of combinatorics 18 (2011), #P17
(see Theorem 3 on page 5 of op. cit., which is exactly what the opening post is asking for, except for a necessary exclusion of $G\cong C^7$.)