# How to reduce 3-COLOR to 42-COLOR?

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$$?

• Do you want to reduce 42-COLOR to 3-COLOR, or the other way around? – Juho Dec 16 '18 at 12:00
• The other way around. $\ 3-COLOR \propto\ 42-COLOR$. Now i noticed my mistake. – 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.