11.11. References 453
Supposefis ann-argument truth function. That is,fWfT;Fgn!fT;Fg:A graphGis called a3-color-f-gateiffGhasndesignatedinput verticesand a
designatedoutput vertex, such that
Gcan be 3-coloredonlyif its input vertices are colored withT’s andF’s. For every sequenceb 1 ;b 2 ;:::;bn 2 fT;Fg, there is a 3-coloring ofGin
which the input verticesv 1 ;v 2 ;:::;vn 2 V.G/have the colorsb 1 ;b 2 ;:::;bn 2
fT;Fg. In any 3-coloring ofGwhere the input verticesv 1 ;v 2 ;:::;vn 2 V.G/have
colorsb 1 ;b 2 ;:::;bn2fT;Fg, the output vertex has colorf.b 1 ;b 2 ;:::;bn/.For example, a 3-color-NOT-gate consists simply of two adjacent vertices. One
vertex is designated to be the input vertex,P, and the other is designated to be
the output vertex. Both vertices have to be constrained so they can only be colored
withT’s orF’s in any proper 3-coloring. This constraint can be imposed by making
them adjacent to the color-vertexN, as shown in Figure 11.28.
(a)Verify that the graph in Figure 11.29 is a 3-color-OR-gate. (The dotted lines
indicate edges to color-vertexN; these edges constrain theP,QandP ORQ
vertices to be coloredTorFin any proper 3-coloring.)
(b)LetEbe ann-variable propositional formula, and supposeEdefines a truth
functionf WfT;Fgn!fT;Fg. Explain a simple way to construct a graph that is
a 3-color-f-gate.
(c)Explain why an efficient procedure for determining if a graph was 3-colorable
would lead to an efficient procedure to solve the satisfiability problem, SAT.
Figure 11.27 GraphGwith no triangles and .G/D 4.