Finding the greatest common divisor of two integers is easier than finding a minimum weight spanning tree. This is, in turn, easier than inverting a matrix which is easier than deciding if two graphs are isomorphic. This may or may not be easier than factoring a large integer. There are thousands of problems that are just as hard as coloring a graph. It may be harder to get an approximate coloring than an approximate answer to almost any other of these equivalent problems.
Nobody knows whether graph coloring is really hard but that is what almost everybody suspects.
Combinatorial Topics of Operations Research.