3SAT polynomial-time many-one reduces to 3-COLORABILITY

First reduce $\phi$ to a not-all-equal $3$-CNF formula. Introduce one global fresh variable $z$ and, for each clause $C_j=({\mathrm{\ell }}_{j1}\vee {\mathrm{\ell }}_{j2}\vee {\mathrm{\ell }}_{j3})$, one fresh variable $s_j$. Replace $C_j$ by the two NAE clauses $N_{j,1}=NAE({\mathrm{\ell }}_{j1},{\mathrm{\ell }}_{j2},s_j)$ and $N_{j,2}=NAE(\mathrm{\neg }{s}_j,{\mathrm{\ell }}_{j3},z)$. Call the conjunction of all these clauses $\psi$. This is polynomial-time and doubles the number of clauses.

The formula $\phi$ is satisfiable if and only if $\psi$ is NAE-satisfiable. If $\phi$ is satisfiable, set $z=0$ and keep the satisfying values of the original variables. Then every original clause has at least one true literal, so the four-tuple $({\mathrm{\ell }}_{j1},{\mathrm{\ell }}_{j2},{\mathrm{\ell }}_{j3},z)$ is not all equal; choose $s_j$ so that the pair of NAE clauses in step 1.1 holds, which is possible exactly because $NAE(a,b,c,d)⟺\mathrm{\exists }s(NAE(a,b,s)\wedge NAE(\mathrm{\neg }s,c,d))$. Indeed, if $a=b=v$, the first clause forces $s=1-v$, and the second then holds exactly unless $c=d=v$. If $a\mathrm{\ne }b$, the first clause allows either $s$; if $c=d=w$, take $s=w$, and if $c\mathrm{\ne }d$, take either value. These cases prove both directions of the identity. Conversely, if $\psi$ is NAE-satisfiable and $z=0$, then each original clause has at least one true literal and $\phi$ is satisfiable. If instead $z=1$, complement every Boolean value. NAE truth is invariant under global complementation, so the complemented assignment still satisfies $\psi$ and now has $z=0$. Thus $\phi$ is satisfiable in all cases.

From $\psi$, build a graph $G_{\psi }$ as follows. Add one distinguished vertex $\nu$. For each variable $u$ appearing in $\psi$, add the triangle on the three vertices $u,\mathrm{\neg }u,\nu$. For each NAE clause with ordered literal occurrences $(a,b,c)$, add a clause triangle with three position-distinguished vertices $(j,1),(j,2),(j,3)$, and join them respectively to the variable-triangle vertices labeled $a,b,c$. The position labels remain distinct even when a literal is repeated. This is polynomial-time and creates $O(\mathrm{\mid }\psi \mathrm{\mid })$ vertices and edges.

Suppose that $\psi$ is NAE-satisfiable. Colour $\nu$ by $2$. In each variable triangle, colour the literal vertices $u$ and $\mathrm{\neg }u$ by their Boolean values $0$ and $1$, which are opposite because they are complements. Now fix one clause triangle. Because the clause is NAE-satisfied, two of its literals have different Boolean values; colour the corresponding two clause vertices by the opposite Boolean values, so each differs from the colour of the adjacent variable vertex. Colour the third clause vertex by $2$. The three clause-vertex colours are then $0,1,2$, so the clause triangle is proper. Doing this for every clause yields a proper three-colouring of $G_{\psi }$.

Suppose conversely that $G_{\psi }$ has a proper three-colouring. Every triangle uses all three colours, so after permuting colour names assume $\nu$ has colour $2$. In each variable triangle, the vertices $u$ and $\mathrm{\neg }u$ therefore receive colours $0$ and $1$ in some order; assign the truth value of each literal to be its vertex colour, so $u$ and $\mathrm{\neg }u$ receive opposite truth values. In each clause triangle, exactly one vertex has colour $2$ and the other two have colours $0$ and $1$. Because each clause vertex is adjacent to the matching literal vertex, a clause vertex with colour $0$ or $1$ forces the corresponding literal to have the complementary truth value. Thus the three literals of the clause are not all equal, so the clause is NAE-satisfied. Therefore $\psi$ is NAE-satisfiable.

Steps 2.1, 3.1, and 4.1 show $\phi \in 3\text{-}SAT⟺\psi \text{ is NAE-satisfiable }⟺G_{\psi }\in 3\text{-}COLORABILITY$. For the empty conjunction the construction is still colourable (only variable triangles, if any, and $\nu$ occur). Map a malformed source string to the complete graph on four vertices, which requires four distinct colours and is a fixed negative instance. Syntax checking and the constructions in steps 1.1 and 2.2 are polynomial-time, so [L1] and [L2] yield a polynomial-time many-one reduction from $3$-SAT to $3$-COLORABILITY.