Hardness of Approximate Coloring