Graph 3-colorability is self-reducible

I am interested in self-reducibility of Graph 3-Coloralibity problem.

Definition of Graph 3-Coloralibity problem.

Given an undirected graph $G$ does there exists a way to color the nodes red, green, and blue so that no adjacent nodes have the same color?

Definition of self-reducibility.

A language $L$ is self-reducible if a oracle turing machine TM $T$ exists such that $L=L(T^L)$ and for any input $x$ of length $n$, $T^L(x)$ queries the oracle for words of length at most $n-1$.

I would like to show in very strict and formal way that Graph 3-colorability is self-reducible.

Proof of self-reducibility of SAT can be used as example (self-reducibility of SAT).

In my opinion, the general idea of proof of self-reducibility of Graph 3-colorability is different from proof of SAT self-reducibility in few aspects.

• SAT has two choices for every literal (true or false) and Graph 3-colorability has three choices (namely, red green blue).

• Choices of SAT literal are independent on each other and choices of colors of Graph 3 colorability are strictly dependent, any adjacent node must have different color, this property potentially could help to make less iteration among all colors.

The general idea of proof.

Let's denote by $c_{v_i}$ the color of the vertex $v_i$, which can take one of the following values (red,green,blue). Define graph $G'$ from a given graph $G$ by coloring the arbitrary vertex $v_0$, assign $c_{v_0}$ to 'red' and put the graph $G'$ with colored vertex $v_0$ to the input of the oracle. If oracle answers 1, which means that the modified graph is still 3-colorable, save the current assignments and start new iteration, with the different vertex $v_1$ chosen arbitrarily, color vertex $v_1$ according to the colors of the adjacent vertices.
if oracle answers 0, which means the previous assignment has broken 3 colorability, pick different color from the set of three colors, but still according to colors of adjacent vertices.

The previous proof is not mat

As Vor mentions in his comment, your reduction doesn't work, since 3-colorability doesn't accept partial assignments of colors. The problem goes even deeper, since setting the color of a single vertex doesn't make any progress in determining whether the graph is 3-colorable: indeed, the graph is 3-colorable iff there is a 3-coloring in which vertex $v$ is assigned color $c$, for any $v,c$ you choose.

Here is a hint on how to solve your exercise, second part. In any 3-coloring of a graph $G$ on more than three vertices, there are two vertices $x,y$ getting the same color (why?). If we merge $x$ and $y$, the resulting graph is still 3-colorable (why?). Try to use this idea to construct a downward self-reducing algorithm for 3-colorability.

Edit: And here is a hint on how to solve the exercise, first part. Consider any two unconnected vertices $x,y$. If there is a coloring in which they get the same color then $G_{xy}$ is 3-colorable (why?), and a coloring of $G$ can be extracted from a coloring of $G_{xy}$ (how?). When will this process stop?

StackExchange Computer Science Q#7013, answer score: 8