Complexity Classes - Models of Computation: Exploring the Power of Computing - page 359

3- COLORING
Instance: The description of a graph G =( V , E ) .
Answer: “Yes” if there is an assignment of three colors to vertices such that adjacent vertices
have different colors.

THEOREM 8.10.4 3- COLORING is NP -complete.
Proof To s h ow t h a t 3 - COLORING is in NP , observe that a three-coloring of a graph can
be proposed in nondeterministic polynomial time and verified in deterministic polynomial
time.
We reduce NAESAT to 3- COLORING . Recall that an instance of NAESAT is an instance
of 3- SAT . A “Yes” instance of NAESAT is one for which each clause is satisfiable with not
all literals equal. Let an instance of NAESAT consist of m cl a uses C = ( c 1 , c 2 , ... , c m )
containing exactly three literals from the set X =

{ x 1 , x 1 , x 2 , x 2 , ... , x n , x n }

of literals in
n variables. (Use the technique introduced in the proof of Theorem 8.10.3 to insure that
each clause in an instance of 3- SAT hasexactlythreeliteralsperclause.)
Given an instance of NAESAT ,weconstructagraph G in log-space and show that this
graph is three-colorable if and only if the instance of NAESAT is a “Yes” instance.
The graph G has a set of n variable tria ng les , one per variable. The vertices of the
triangle associated with variable x i are .(SeeFig. 8.14 .) Thus, all the variable

triangles have one vertex in common. For each clause containing three literals we construct
one clause triangle per clause. If clause c j contains literals λ j 1 , λ j 2 ,and λ j 3 , its associated
clause triangle has vertices labeled ( j , λ j 1 ) , ( j , λ j 2 ) ,and ( j , λ j 3 ) . Finally, we add an edge
between the vertex ( j , λ j k ) and the vertex associated with the literal λ j k .
We now show that an instance of NAESAT is a “Yes” instance if and only if the graph G
is three-colorable. Suppose the graph is three-colorable and the colors are

{ ν , x i , x i }

{ }

0, 1, 2 .Since

ν

Variable Triangle

x 1 x 1 x 2 x 2 x 3 x 3

Clause Triangle

( 1, x 1 ) ( 2, x 1 )

( 1, x 2 ) ( 1, x 3 ) ( 2, x 2 ) ( 2, x 3 )

Figure 8.14 Agraph G corresponding to the clauses c 1 = {x 1 , x 2 , x 3 } and c 2 = {x 1 , x 2 , x 3 }
in an instance of NAESAT . It has one variable triangle for each variable and one clause triangle for
each clause.