Non-deterministic Turing machine to solve graph colouring
The algorithm would be as follows:


Go through each vertex and "guess" a coloring using non-determinism. This takes time $O(V\log n)$, since this is the time it takes to write all the colors. 
Check that the coloring is legal, which also takes polynomial time. If it's not legal, it rejects, and otherwise it accepts. 


By definition, a non-deterministic Turing machine accepts an input if there is some accepting computation path. So the machine accepts iff some valid coloring exists.