complexity of CSPs with 2-variable constraints and multi-valued variables

(CSP = "constraint satisfaction problem")

CSPs for which either the variables are restricted to less than two values or the constraints
take less than two inputs are obviously trivial, and Schaefer's dichotomy theorem
gives the complete situation for variables with two possible values.
How hard is it to solve CSPs with 2-variable constraints
but variables that can take more than two values?

add a variable $x_i \in \{1,2,3\}$ for each node; then for each edge $(x_i,x_j)$ add the constraint $x_i \neq x_j$
Schöning's algorithm runs in time $O\left(\left(\frac{d(k-1)}{k}\right)^n\right)$, where $k$ is the clause width and $d$ is the number of possible values per variable.
• For (3,2)-CSP I think that the current best is $O(1.3645^n)$ (n is the number of variables) by Richard Beigel and David Eppstein Feb 11 '14 at 23:26