# Paths in Coloured Graphs

• November 3rd 2010, 07:43 AM
Newtonian
Paths in Coloured Graphs
Suppose $\chi(G)=k$ and $c:V(G) \rightarrow \{1,\ldots,k\}$ is a proper $k$-colouring of $G$. Must there be a path $x_1 \ldots x_k$ in $G$ with $c(x_i)=i$ for each $i$?

I've been trying to find a counter-example without any luck (but on the other hand can't come up with a proof either...)
• November 7th 2010, 09:37 AM
nimon
Take a look at the Gallai-Roy-Vitaver theorem and its corollaries. Apparently, a proof can be found in this article but you might be better to find the original somewhere.