Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to enumerate the vertices of $G$ and delete any vertex that if your decision function tells you is not in the clique) But for 3-COLOR problem, I have no idea of how to link decision problem to search problem. Can anybody help me?

Let the vertices of the input graph $G$ be $\{v_1, \dots, v_n\}$. First, check if $G$ is 3-colourable: if not, output "No 3-colourings" and quit.

Otherwise, add new vertices called $r$, $g$ and $b$ to $G$ and add the edges $rb$, $bg$ and $br$. Call this graph $G_0$. Note that $G_0$ is 3-colourable and, in any 3-colouring of $G_0$, the three new vertices must receive different colours. Since the names of the colours are arbitrary, we will call the colour that $r$ gets, red; call $g$&'s colour, green; and call $b$'s colour blue.

We'll now create a sequence of graphs $G_1, \dots, G_n$, each of which will be 3-colourable, creating $G_i$ from $G_{i-1}$ as follows.

• Set $G_i = G_{i-1} + \{rv_i, gv_i\}$ (i.e., the graph made by adding edges $rv_i$ and $gv_i$ to $G_{i-1}$) if this graph is is 3-colourable. Since $v_i$ is adjacent to both $r$, which is red, and $g$, which is green, $v_i$ must be blue.

• Otherwise, set $G_i = G_{i-1} + \{gv_i, bv_i\}$, if this graph is 3-colourable. In this case, $v_i$ must be red.

• Otherwise, set $G_i = G_{i-1} + \{bv_i, rv_i\}$. Since $G_{i-1}$ was 3-colourable (you can prove this by induction), and we couldn't find a colouring with $v_i$ blue or red, $v_i$ must be green.

The above procedure produces a 3-colouring of the $n$-vertex graph $G$ with $2n+1$ calls to the oracle (procedure) for checking 3-colourability.

StackExchange Computer Science Q#32444, answer score: 6