Graph threecoloring has been shown to be in a class of problems known as NPComplete. In a nutshell, NPComplete problems are considered the hardest problems in the class of nondeterministically solvable problems given the constraint of polynomial time. [1] In essence, these problems cannot be solved by a deterministic computer (such as all current computer models based on a Turingmachine) in less than exponential time. Another interesting fact about all NPComplete problems is that every problem in this class can be mapped to any other in polynomial time. This implies that if a polynomial time algorithm were found for a single problem in this class, we could then find a polynomial time algorithm for all problems in this class. As of current research, there is no proof showing that a polynomial time algorithm does or does not exist for these problems. [1] 
Some Examples of NPComplete Problems:

1. Garey, Michael A. and Johnson, David S. Computers and Intractability. 1979.