## 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.