Question

a) Show that the problem of k-colorability is reduced to the problem of (k + 1)-colorability.

b) We know that the problem of 2-colorability is in class P. Can we then deduce from question a) above that problem of 3-colorability is also in class P? Explain your answer.

Answer 1

a. Problem of k-colorability can be reduced to k+1 colorability by given the graph G=(V,E) where we have to check whether k-colorability exist for this graph, can be reduced to graph G'=(V',E') for problem instance of (k+1)-colorability by adding a new vertex v which will be connected with all other vertices of V in G=(V,E). Now if k-coloring exist for original graph G, then since vertex v is connected with every other vertices of V, therefore vertex v has to be assigned a different colour than colour of other vertices. Therefore if k-colouring exist for graph G then k+1 coloring exist for graph G'. Similarly if k+1 coloring exist for graph G' then since additional vertex v has different colour then all other vertices therefore by removing vertex v from G' to make original graph G, G will have atmost k-colours. So this reduction is correct.

So k-colorability is polynomial time reducible to (k+1)-colorability.

b. Reducing 2-colorability problem which is in P into a 3-colorability problem does not means that 3-colorability problem is also in P. If 3-colorability problem could be reduce in polynomial time to 2-colorability problem then we can definitely say that 3-colorability problem is in P. But since the reverse side is not true. Therefore reduction from 2-colorability problem to 3-colorability problem does not means 3-colorability is in NP.

Please comment for any clarification.