The main result of this paper is a proof that the three-coloring problem can be solved in worst-case time O(1.3289n). The previous record for this problem was the O(1.415n) result of Schiermeyer [1]. The proof is based on the interesting idea that it is sufficient to constrain the problem by restricting each vertex to two of the three colors, since such a constraint problem can be solved in polynomial (P) time as an instance of 2-satisfiability (2-SAT). A simple application of this idea already produces an O(1.5n) time-randomized algorithm.