
Paths in Coloured Graphs
Suppose $\displaystyle \chi(G)=k$ and $\displaystyle c:V(G) \rightarrow \{1,\ldots,k\}$ is a proper $\displaystyle k$colouring of $\displaystyle G$. Must there be a path $\displaystyle x_1 \ldots x_k$ in $\displaystyle G$ with $\displaystyle c(x_i)=i$ for each $\displaystyle i$?
I've been trying to find a counterexample without any luck (but on the other hand can't come up with a proof either...)

Take a look at the GallaiRoyVitaver theorem and its corollaries. Apparently, a proof can be found in this article but you might be better to find the original somewhere.