Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Solutions are available.

1. D4G3C

The GRAPH 3-COLORABILITY problem asks if it is possible to color all the vertices of a graph with no more than three colors, so that every edge has different-colored endpoints. It is well known that GRAPH 3-COLORABILITY is NP-complete.

Suppose that we restrict the problem to graphs where every vertex has at most four neighbors. Show that this restricted problem DEGREE 4 GRAPH 3-COLORABILITY of finding whether a graph with maximum degree 4 can be colored with three or fewer colors is also NP-complete, or give a polynomial-time algorithm that solves it. (Extra credit if you do both.)

2. D4G2C

Suppose now that we change the number of colors for D4G3C from three to two. Show that the resulting problem DEGREE 4 GRAPH 2-COLORABILITY of finding whether a graph with maximum degree 4 can be colored with two or fewer colors is also NP-complete, or give a polynomial-time algorithm that solves it. (Extra credit if you do both.)