The 3-Coloring Problem Given an undirected graph G=(,E),it is required to color each vertex in Vwith one of three colors,say 1, 2,and 3,such that no two adjacent vertices have the same color.We call such a coloring legal;otherwise, if two adjacent vertices have the same color,it is illegal. A coloring can be represented by an n-tuple(G, G2,,Cn)such that c∈{1,2,3}，1≤kn. For example,(1,2,2,3,1)denotes a coloring of a graph with five vertices.The 3-Coloring Problem ◼ Given an undirected graph G=(V, E), it is required to color each vertex in V with one of three colors, say 1, 2, and 3, such that no two adjacent vertices have the same color. We call such a coloring legal; otherwise, if two adjacent vertices have the same color, it is illegal. ◼ A coloring can be represented by an n-tuple (c1 , c2 , …, cn ) such that ci{1, 2, 3}, 1in. ◼ For example, (1, 2, 2, 3, 1) denotes a coloring of a graph with five vertices