MHB Solving Decision Problem with k Colors - NP-Complete

[evinda]

Hello! (Wave)

I had a test today and a question was to make a decision problem for the coloring using at most $k$ colors and to show that this problem is NP-complete.

Is the following right?

Decision problem: Is there a coloring with $k$ colors?

Also could we show that the problem is in NP as follows?

A non-deterministic Turning machine first guesses the nodes that are colored with each of the $k$ colors and then it verifies in $\Theta(E)$ time that each adjacent nodes of the graph have a different colour.
Thus the problem is in NP.

 

[Evgeny.Makarov]

This seems OK. There is still the completeness part missing.

 

[evinda]

This seems OK.

(Happy)

There is still the completeness part missing.

Oh, I am sorry.. we had just to prove that it is in NP, not that it is NP-complete.Then the exercise required to explain, but not to prove if 3-coloring is NP-complete.

I wrote that it is NP-complete, because it can be reduced to the 3SAT problem, which is known to be NP-complete. Do you think that it is enough? (Thinking)

 

[Evgeny.Makarov]

Then the exercise required to explain, but not to prove if 3-coloring is NP-complete.

I wrote that it is NP-complete, because it can be reduced to the 3SAT problem, which is known to be NP-complete.

Reducing 3-coloring to 3SAT does not help in any way.

 

[evinda]

Reducing 3-coloring to 3SAT does not help in any way.

Oh yes, right... (Tmi)
We could say that we can reduce 3SAT to 3-coloring, right?

 

[Evgeny.Makarov]

Yes. I don't know the details of the reduction, though.

 

[evinda]

Yes. I don't know the details of the reduction, though.

Ok, no problem... (Smile)

Thanks a lot for your answer! (Happy)