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
-
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$– Mikhail TikhomirovCommented 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$– Peter HeinigCommented Sep 28, 2017 at 10:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.)
answered Sep 28, 2017 at 10:29
-
$\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$ Commented Sep 28, 2017 at 10:41