The requirement is that two adjacent vertices have different colors, and max. 42 colors.

I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes complicated.

Is it similar to $ k\text{-COLOR} $ for any $k$?

  • $\begingroup$ Do you want to reduce 42-COLOR to 3-COLOR, or the other way around? $\endgroup$ – Juho Dec 16 '18 at 12:00
  • $\begingroup$ The other way around. $\ 3-COLOR \propto\ 42-COLOR $. Now i noticed my mistake. $\endgroup$ – gil Dec 16 '18 at 12:27

For an instance of 3-COLOR, try to add a complete graph of size $k-3$, and add an edge between each new vertex and each old vertex. Now you can prove the new graph is $k$-colorable iff the old graph is 3-colorable.

| cite | improve this answer | |

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.