3-coloring in time O(1.3289n)

We consider worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a, b)-CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2, 3)-CSP while 3-coloring and various related problems are special cases of (3, 2)-CSP; there is also a natural duality transformation from (a, b)-CSP to (b, a)-CSP. We show that n-variable (3, 2)-CSP instances can be solved in time O(1.3645(n)), that satisfying assignments to (d, 2)-CSP instances can be found in randomized expected time O((0.4518d)(n)); that 3-coloring of n-vertex graphs can be solved in time O(1.3289(n)); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645(n)); that 3-edge-coloring of n-vertex graphs can be solved in time O(2(n/2)), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(n(O(1)) + 1.3645(t)). (C) 2004 Elsevier Inc. All rights reserved.