Non-deterministic Turing machine to solve graph colouring Consider the graph coloring problem: given an undirected graph $G$ and a natural number $n$ return yes if we can color the graph with n different colors and no otherwise.

I am able to design a deterministic Turing machine that would solve it with a greedy approach trying the different combinations of coloring with the $n$ colors. I think this takes exponential time although I'm not sure how to proof it.  

However, I am not able to conceive a nondeterministic Turing machine that would do so. Can someone guide me designing an algorithm for this machine?
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.