Graph 3-colorability is self-reducible

Question

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 mathematical robust, the question is how to improve it and to make it more formal and mathematical strict. It looks like I need more carefully distinguish the cases when new vertex doesn't have any edges with already colored vertices and when the new vertex is adjacent to already colored vertices.

In addition I would like to prove that Graph 3-colorability is downward self-reducible.

Definition of downward self-reducible language.

The language $A$ is said to be downward self-reducible if it is possible to determine in polynomial time if $x \in A$ using the results of shortest queries.

The idea seems to be simple and intuitive: start with coloring an arbitrary vertex, and on each iteration add one more colored vertex and check by oracle if graph is still 3-colorable, if not reverse previous coloring and check another color.

But how to write the proof in a strict way and more important how to find an appropriate encoding of a graph.

In short, I would like to show that Graph 3-colorability is self-reducible and downward self-reducible in strict and formal way.

I will appreciate sharing your thoughts with us.

Update:

downward self-reducibility

Downward self-reducibility is applied to decision problem and it's oracle answers the same decision problem with shorter input, at the end of the process of downward self-reduction we should have the right color assignments.

Every 3 - colorable graph $G$ with more than three vertices, has two vertices $x,y$ with the same color. Apparently, there is only three colors and more than three vertices so some number of non-adjacent vertices might have the same color. If we merge $x$ and $y$ with the same color as the result we still have 3 - colorable graph, just because, if graph is 3 - colorable, then there are exist right assignment of all vertices that are adjacent to $x$ and $y$ according to the same color of $x, y$, so by merging $x, y$ we don't need to change any color of any vertices, we only need to add more edges between already correctly colored vertices (I know it's not the best explanation, I will appreciate if someone could explain it better). On every iteration we take two non-adjacent vertices $x,y$ of graph $G$, merge $x$ and $y$ and get graph $G'$ which is our shorter input to the oracle. Oracle answers if it's 3-colorable or not. Now the problem is before setting $G'$ on the input of oracle I should color the merged vertex and test colorability of $G'$, if it's not 3-colorable change the color, but how to implement it correctly, I need right encoding for it.

self-reducibility

First, we should check if a given graph $G$ is 3-colorable at all, so set it on input of oracle, and oracle will answer if it's 3 - colorable, if yes then start the process. Any two nonadjacent vertices can have the same color in 3-colorable graph. The process of self-reducibility we should run in iterations, I think we can start from small subgraph $G'$ of a given graph $G$ and on every iteration add one more vertices from $G$ to $G'$. In paralel, we should maintain the assignment of already colored vertices. Unfortunately, I still don't get the idea completely. Would appreciate for help and hints.

Answer 1

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?