# 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?

• Are you sure that you know what a non-deterministic Turing machine is? – Yuval Filmus Apr 15 '15 at 18:59
• I guess, a machine that can go in multiple states given a word on the tape? – revisingcomplexity Apr 15 '15 at 19:13
• Something of that sort. – Yuval Filmus Apr 15 '15 at 19:14

1. 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.
• where does the $log(n)$ come from? – revisingcomplexity Apr 15 '15 at 19:23
• It's the number of cells it takes to represent a color. Even this complexity only holds for a multitape machine, since in parallel you also need to count up to $n$ (and up to $V$). – Yuval Filmus Apr 15 '15 at 19:48