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?
With 3 values and binary relations, the CSP is still NP-complete (it is denoted with (3,2)-CSP). A quick reduction is from graph coloring:

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$