Graph Coloring Decision Problem Reduction to Prove NP-Complete

Question

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?

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.