More NP-Complete Problems

Often in problems with a parameter k like k-CNFSat and k-colorability, larger values of k make the problem harder. This is not always the case. Consider the problem of determining whether a planar graph has a k-coloring. The problem is trivial for k = 1, easy for k = 2 (check by DFS or BFS whether the graph is bipartite, i.e. has no odd cycles), and trivial for k = 4 or greater by the Four Color Theorem, which says that every planar graph is 4-colorable. This leaves k = 3. We show below that 3-colorability of planar graphs is no easier than 3-colorability of arbitrary graphs. This result is due to Garey, Johnson, and Stockmeyer [40]; see also Lichtenstein [72] for some other NP-completeness results involving planar graphs.