To reduce 3CNF to 3COL, for a given formula F construct the
following graph G:
The vertices of G are all the variables of F, plus their
negations, plus 5 vertices for each clause, and 3 special
vertices: TRUE, FALSE, BLUE.
There are two types of edges:
Type 1: For each variable x:
BLUE
/\
/ \
/ \
x-----(-x)
and also a triangle on TRUE, FALSE, BLUE.
Type 2: For every clause (a v b v c) we have the following
widget:
a------O
|\
| O----O
|/ |\
b------O | \
| \
| TRUE
| /
| /
|/
c-------------O
note that this widget is 3col by TRUE, FALSE, BLUE, iff
exactly one of a,b,c is colored TRUE (ie., the clause is
true).