# 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. Sep 28, 2017 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'.) Sep 28, 2017 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$.)