Question

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..

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top