Homework 4

1. Exercise 1.1 (page 7) from Vazirani book.
2. Exercise 1.4 (page 8) from Vazirani book.
3. Given a graph G = (V, E), a vertex coloring is an assigment of a color to each vertex in V such that two vertices connected by an edge do not have the same color.

   The vertex coloring problem takes as input a graph G, and produces a vertex coloring of G with the minimum possible number of colors.

   Consider the following algorithm: Pick an uncolored vertex, and color it with the first color not yet used by one of its neighbors.

   Is this an approximation algorithm for vertex coloring? Prove an approximation bound, or construct a sequence of examples that show that this algorithm can be arbitrarily bad.

4. Exercise 2.1 (page 22) from Vazirani book.
5. Exercise 2.2 (page 23) from Vazirani book.