CS 5315 Homework #13

Date Assigned: Tuesday, April 12, 2005

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.