0
$\begingroup$

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color?

I'm aware we can show that 3-colorable is an NP-complete problem by reducing 3-SAT to it. But I'm wondering is it possible to reduce clique to it?

I know for example that if a graph with n vertices contains a subgraph which is a clique of size k, then you need at least k colors (that is, the chromatic number is at least k).

So could we say that if a graph contains a clique of size 4, then it is not 3-colorable, and vice versa?

Edit: Hmm..upon further thought, maybe the reduction wouldn't work because in order to reduce clique, you can't fix ahead of time that you're looking for a clique of size 4? The size of the clique would be arbitrary..

Improve this question
$\endgroup$
1
  • $\begingroup$ What have you tried? Have you tried looking for a proof of your claim? Have you tried looking for a counterexample? Try some small graphs. $\endgroup$
    – D.W. ♦
    Commented Mar 9, 2016 at 16:26

2 Answers 2

Reset to default
3
$\begingroup$

A problem $P$ being NP-hard means that all problems in NP can be reduced to $P$. That's by definition. Working out the exact reduction needed can be tricky, which is why one usually looks for a somehow similar problem to prove hardness. You probably wouldn't try to directly reduce MINIMUM INTERVAL GRAPH COMPLETION to Tetris to prove its hardness.

In general you can chain reductions. In your case, since you know 3-colorability can be used to solve 3-SAT and you know 3-SAT can be used to solve CLIQUE, you can first transform your CLIQUE instance to 3-SAT and then the resulting formula to a 3-colourability problem.

Improve this answer
$\endgroup$
5
$\begingroup$

No, you couldn't say that, because it's not true.

A helpful method is to prove all your claims. Don't just guess -- try to find a proof. If you're struggling to find a proof, the first thing to check is whether maybe the thing you're trying to prove is false, so look for a counterexample. In this case you should easily be able to find a counterexample to your claim. Alternatively, if you can't find a proof and can't find a counterexample, look for a different approach or a different way to solve the problem that uses only facts you do know how to prove correct.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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