I am trying to show that the NP-Complete problem of 3-coloring a graph reduces to the problem of 10-coloring a graph.I have already shown how 10-coloring can be verified in polynomial time, and is thus in NP. Now I just need to show it indeed can be reduced to 3-coloring.

My thinking was to essentially prove a bi-conditional: given a graph G, we have that G has a 3-coloring iff G has a 10-coloring. Now, I am not sure how to go about showing this since, fairly obviously, G could have a 10-coloring and not a 3-coloring. So this leads me to believe that there must be some reduction that alters G in some way that lets me see that, yes, 3-coloring does reduce to 10-coloring. Problem is, I am having a difficult time visualizing this.

Can anyone help me out?

  • $\begingroup$ The bi-condition you took first is wrong as you yourself pointed out. For a (Turing) reduction from graph Problem A(here 3-coloring) to graph Problem B(here 10-coloring), all you need is to show that given a graph $G$, you can construct a graph $H$ such that $G$ is an yes instance of Problem A iff $H$ is an yes instance of Problem B. For most reductions, graph $H$ will not be same as graph $G$ $\endgroup$ – Cyriac Antony Apr 28 '19 at 3:56

3-coloring a graph is reducible to 10-coloring by a padding argument. Given a graph $G$ that you need to 3-color, create a new graph $H$ by adding the complete graph $K_7$ and making an edge from each of its vertices to all the vertices of $G$. The $K_7$ part of $H$ obviously cannot be colored with less than seven colors. None of those seven colors can be used in the coloring of the rest of $H$ because those vertices are adjacent to all the vertices of the $K_7$ part. So you can only 10-color $H$ if you can find a 3-coloring of the rest of $H$ with three new colors. The rest of $H$ is of course isomorphic to $G$ which means finding the 10-coloring for $H$ is just as hard as finding a 3-coloring for $G$.

This reduction can be done for any graph $G$ in polynomial time and therefore proves the NP-hardness of 10-coloring.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.