Theory of Computations,
Quiz 2 for the course
CS 5315, Spring 2012

Name ___________________________________________________

1. Prove that the 5-coloring problem -- given a graph, check whether it can be colored in 5 colors -- is NP-hard.