Coloring graph with maximum vertex degree $< k$ so every vertex is a starting point for a path containing each color

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 paths you are talking about actually have nothing to do with Hamiltonian paths, right? Better edit the title and the tags. – Mikhail Tikhomirov Sep 28 '17 at 9:37
• Dear @Userbejian29: please note that your use of "bounded degree" is sort-of-a-misuse of standard graph-theoretic terminology: 'bounded degree' is used if the context contains an infinite sequence of graphs. (Search for yourself.) What you mean is simple 'with maximum degree $<k$'. This is a usual way to put it. Would you please say it this way? (Unless for some strange reason you really really insist on this unusual use of 'bounded degree'.) – Peter Heinig Sep 28 '17 at 10:17

(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$.)