
Chapter 14: Logic Programming and Parallel Complexity
569
Figure
3:
Illustrating the Proof of Theorem
2
Figure 3a by unique subgraphs, and will be omitted. One can show that H(G)
is bounded iff G is three-colorable.
"If" Let G be three-colorable, then the above sirup is equivalent to the fol-
lowing sirup:
R(x,y,z,v) R(x,y,
z
,w), R
1
(x,v),R
1
(y,v),R
1
(z,v),R
2
(w,x),R
2
(w,y),
R
2
(w,z),
R
3
(x,y),R3(y,x),R3(z,x),R3(x,z),R3(z,y),R
3
(y,z).
This is represented in Figure 3b. For this all one has to note is that Figure 3a
(3b) can be homomorphically mapped in Figure 3b (3a), where x,y,z,v,w are