Suppose and is a proper -colouring of . Must there be a path in with for each ?

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

Printable View

- Nov 3rd 2010, 06:43 AMNewtonianPaths in Coloured Graphs
Suppose and is a proper -colouring of . Must there be a path in with for each ?

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...) - Nov 7th 2010, 08:37 AMnimon
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.