I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here:

Given a graph $G = (V, E)$ where $V$ is the set of vertices and $E$ is the set of edge relations, can you assign some given set of colors to $G$ such that two vertices that are connected by an edge are not assigned the same color.

I have found a number of different proofs demonstrating the problem's NP-Completeness by a reduction from another known NP-Complete problem. However, after seeing a reduction from the 3-SAT problem to the 3-Coloring problem, I began to wonder if the SAT problem is reducible to the k-Coloring problem directly and not transitively. I tried looking into it and I cannot seem to find anywhere that describes such a reduction.

So, my question is, does anyone know if a reduction from SAT to k-Coloring has already been done? If so, what does it look like/how does it work? Are there any papers out there that I simply missed that go over this problem?


1 Answer 1


SAT can be reduced to 3-SAT in a straightforward way (the Tseitin transform), and you seem to be aware that 3-SAT can be reduced to 3-coloring (e.g., https://www.cs.toronto.edu/~lalla/373s16/notes/3col.pdf, https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture7.pdf), and 3-coloring can be reduced to $k$-coloring in a straightforward way (just set $k=3$).

Then it is straightforward (but tedious) to compose the reductions and obtain a direct reduction from SAT to $k$-coloring. I don't think it will add any insight beyond knowing how each of those individual reductions work, but you can certainly construct it.

  • $\begingroup$ Any NP-Complete problem can be reduced to one another since, by definition, they are all equally hard (under polynomial reducibility). As pointed out by @D.W., it might not be worthwhile trying to get into a complicated reduction in this case compared to the existing convenient two-step proof. $\endgroup$
    – codeR
    Commented Apr 30 at 9:34
  • $\begingroup$ Yeah that all makes sense. I am aware of the multi-step proof to show that k-coloring is in NP-Complete from SAT to 3-SAT to 3-Coloring to k-Coloring, and I am also aware that theoretically, all NP-Complete problems must be able reduce to one another by definition in some way. I was just interested in seeing if anyone was aware of the existence of a proof that showed that SAT can reduce directly to k-coloring. However, I do also understand that understanding/spending time on a proof like this is basically a waste of time but, that didn't stop me from being curious. $\endgroup$
    – Darien
    Commented May 1 at 22:40

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.