  With domains of size 2, a CSP problem is just a satisfiability problem, so Schaefer’s theorem already established the Feder and Vardi conjecture for this case. A simple instance of a CSP with domain size 3 is the 3COLOR problem for undirected graphs.  Given such a graph, G, can the vertices of G be colored one of three colors so that no two adjacent vertices have the same color?  To write this as a CSP, let \(D = \{R,Y,B\}\) be a set of three distinct colors and let the relation \(N\) be the not-equal relation  on \(D\).  Then from \(G=(V,E)\) the instance of 3COLOR is \[ \varphi_G \quad = \quad \bigwedge_{(u,v)\in E} N(u,v)\; .\] Note that \(\varphi_G\) says that whenever there is an edge in \(G\) between vertices \(u\) and \(v\), then \(u\) and \(v\) are assigned different colors. 