  We consider worst case time bounds for NP-complete problems including 3-SAT,
3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a
constraint satisfaction (CSP) formulation of these problems; 3-SAT is
equivalent to (2,3)-CSP while the other problems above are special cases of
(3,2)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the
time bounds for solving the other problems listed above. Our techniques involve
a mixture of Davis-Putnam-style backtracking with more sophisticated matching
and network flow based ideas.
