Due Date: Thursday, April 14, 2005
1. Prove that 4-coloring is NP-hard. For extra credit: Prove that 5-coloring is NP-hard.
2. For extra credit: complete the proof - that 3-coloring is NP-hard - that we started in the class; specifically: use the or-gadget to take care of triple disjunctions like a \/ b \/ c.