Joseph C. Culberson's WWW page on graph coloring, http://web.cs.ualberta.ca/~joe/Coloring/, provides an extensive bibliography and a collection of programs to generate hard graph coloring instances.