Grover's search algorithm for 3 coloring According to Arora &amp; Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in $O(\text{poly}(n)2^{n/2})$ time a string $a$ such that $f(a) = 1$ (if such a string exists).

My question is an application of Grover's algorithm to 3 coloring. How can you show, using Grover's algorithm, that 3-coloring can be solved on a quantum computer in time $O(\text{poly}(n)2^{n/2})$, where $n$ is the number of vertices?

This is not a direct application of the algorithm, since although you can easily encode each of the $3^n$ (valid and invalid) colorings of the $n$ vertices using $\log_2(3^n) = n\log_2(3) = O(n)$ bits, this means that Grover's algorithm gives a run time of $O(\text{poly}(n)2^{n\log_2(3)/2}) = O(\text{poly}(n)3^{n/2})$.

So maybe, you would need to show that a coloring (possibly valid) can be encoded using only $n + O(1)$ bits? How would you show that?
You don't need to keep track of all $3$ colours for your colouring, because we know how to two colour quickly. 

Let the colours be $\{0,1,2\}$. Have an oracle $f: \{0,1\}^{|V|} \rightarrow \{0,1\}$ that you interpret as selection a subset $C_0 \subseteq V$ that you will pretend is $0$-coloured. Your circuit then (1) in polynomial time checks if $V - C_0$ is two-colourable with $\{1,2\}$, and (2) in polynomial time checks if $C_0$ is an independent set. If both are true then it returns $1$, else $0$. Now you are searching over only $2^n$ database entries for a marked element and so have the runtime you wanted.