# Existence of rainbow paths in graphs?

Let $G$ be a graph, and let $c: V(G) \to \{1,\dots,k\}$ be a proper $k$-colouring of $G$. We say that a path $v_1 \dots v_k$ in $G$ is a rainbow path of this colouring if $c(v_i) = i$ for every $i \in \{1,\dots,k\}$. Now suppose that $k = \chi(G)$, the chromatic number of $G$; I am trying to determine whether or not a rainbow path exists for this colouring.

I don't really know where to start, though. If $k = 2$, then a rainbow path certainly exists; for the case $k = 3$, I've tried looking at cycles of odd length and wheels with an odd number of spokes and it seems that such graphs must always have rainbow paths as well, but I'm not sure how to generalize to general graphs with $\chi(G) = 3$ or to higher values of $k$.

Any help is appreciated!

-
Is the order of the coloring important? If $k=3$, say, would a path with colors $2,1,3$, say, count as a rainbow path? – Samuel May 12 '13 at 22:14
@Samuel Good point. I want to say that the order of the coloring does indeed matter, but I'm not entirely sure. The examples I've worked out contain both rainbow paths and "generalized rainbow paths" like the one you described. I'm trying to see whether the existence of a generalized rainbow path implies the existence of a rainbow path... – Jonas May 12 '13 at 22:36

The answer is yes.

We may without loss of generality assume that $G$ is connected; otherwise we throw away each component with lower chromatic number, and consider every other component individually.

For $k=3$: Let $E_1$ be the set of all vertices with the color $1$. Let $E_2$ be the set of all vertices adjacent to a vertex in $E_1$ with the color $2$. If there is no such vertex, then all vertices in $E_1$ could be recolored to the color $2$, and we have a $(k-1)$-coloring of $G$; contradiction. Let $E_3$ be the set of all vertices adjacent to a vertex in $E_2$ with the color $3$. If there is no such vertex, then we could recolor $E_1$ to the color $2$ and $E_2$ to the color 3, and obtain a 2-colorable graph; contradiction. Therefore $E_1,E_2,E_3$ are nonempty, so we can find a rainbow path $e_1,e_2,e_3$ where $e_i\in E_i$.

This argument can be carried on for general $k$: Let us continue. Let $E_4$ be the set of vertices adjacent to $E_3$ which have the color $4$. If it were empty, then we could recolor $E_1,E_2,E_3$ to the colors $2,3,4$, respectively, and obtain a $(k-1)$-coloring of $G$; contradiction. We can define $E_5,\ldots,E_k$ analogously. When we are done, we can choose a rainbow path $e_1,\ldots,e_k$ where $e_i\in E_i$ for each $i$.

-
I'm not totally clear on why $E_3$ is necessarily non-empty. The logic is clear to me for $E_2$, but surely there could be a vertex of colour $3$ adjacent to a vertex of colour $2$ that is not in $E_2$? – user73445 May 12 '13 at 22:50
@user73445 And that adjacent vertex could then be recolored with 1, causing the former vertex with color 3 to be recolorable as well if it is not already in E3.. – Sh3ljohn May 12 '13 at 23:02
@user73445: Sure there can. But if you suppose that $E_3$ is empty, then $E_2$ has no neighbors of color $3$. Now recolor $E_1$ to the color $2$, and recolor $E_2$ to the color 3. This is still a coloring of the graph since $E_2$ had no neighbors of color 3, and now we have obtained a coloring of $G$ without the color $1$, a contradiction, which shows that $E_3$ could not have been empty. – Samuel May 12 '13 at 23:05
@Samuel: perfect, thanks! – user73445 May 12 '13 at 23:10
@Samuel Great explanation, and an unexpectedly appropriate profile picture as well! :) – Jonas May 12 '13 at 23:17