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?

  • 2
    $\begingroup$ The paths you are talking about actually have nothing to do with Hamiltonian paths, right? Better edit the title and the tags. $\endgroup$ Sep 28, 2017 at 9:37
  • $\begingroup$ 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'.) $\endgroup$ Sep 28, 2017 at 10:17

1 Answer 1


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

  • $\begingroup$ @MikhailTikhomirov: thanks for pointing out. This is not my intent. I find the 'reference request' section, within reason, very valuable. I will edit the answer. But an answer it is, I think. (Though it should be Theorem 3, not 1). I will edit. $\endgroup$ Sep 28, 2017 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.