Algorithm Analysis Graph coloring

Mapmakers try to use as few colors as possible when coloring countries on a map, as long as no two countries that share a border have the same color. We can model this problem with an undirected graph G D .V; E/ in which each vertex repre- sents a country and vertices whose respective countries share a border are adjacent. Then, a k-coloring is a function c W V ! f1; 2; : : : ; kg such that c.u/ c.#/ for every edge .u; #/ 2 E. In other words, the numbers 1; 2; : : : ; k represent the k col-ors, and adjacent vertices must have different colors. The graph-coloring problem is to determine the minimum number of colors needed to color a given graph.

a. Give an efficient algorithm to determine a 2-coloring of a graph, if one exists.

--------------------------------------------------

b. Cast the graph-coloring problem as a decision problem. Show that your deci-sion problem is solvable in polynomial time if and only if the graph-coloring problem is solvable in polynomial time.

--------------------------------------------------

c. Let the language 3-COLOR be the set of graphs that can be 3-colored. Show that if 3-COLOR is NP-complete, then your decision problem from part (b) is NP-complete.

To prove that 3-COLOR is NP-complete, we use a reduction from 3-CNF-SAT. Given a formula ' of m clauses on n variables x1, x2,..., xn, we construct a graph G D .V; E/ as follows. The set V consists of a vertex for each variable, a vertex for the negation of each variable, 5 vertices for each clause, and 3 special vertices: TRUE, FALSE, and RED. The edges of the graph are of two types: literal edges that are independent of the clauses and clause edges that depend on the clauses.

The literal edges form a triangle on the special vertices and also form a triangle on xi, :xi, and RED for i D 1; 2; : : : ; n.

--------------------------------------------------