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?
Best Answer
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.