a graph coloring which satisfies a given set of constraints. Formally, it is specified as a formula, $\varphi(A)$, where $A$ is an $n\times n$ adjacency matrix of integer variables with domain $\{0\}\cup [k]$ and $\varphi$ is a constraint on these variables. A solution is an assignment of integer values to the variables in $A$ which satisfies $\varphi$ and determines both the graph edges and their colors. We often refer to a solution as an integer adjacency matrix and denote the set of solutions as $sol(\varphi(A))$.

Figure \[fig:gcp\] presents the $k$-color graph coloring problems we focus on in this paper: $(r_1,\ldots,r_k;n)$ Ramsey colorings. Constraint (\[constraint:simple\]), $\varphi_{adj}^{n,k}(A)$, states that the graph represented by matrix $A$ has $n$ vertices, is $k$ colored, and is simple. Constraint (\[constraint:nok\]) $\varphi_{r}^{n,c}(A)$ states that the $n\times n$ matrix $A$ has no embedded sub-graph $K_r$ in color $c$. Each conjunct, one for each set $I$ of $r$ vertices, is a disjunction stating that one of the edges between vertices of $I$ is not colored $c$. Notation: $\wp_r(S)$ denotes the set of all subsets of size $r$ of the set $S$. Constraint (\[constraint:coloring\]) states that $A$ is a $(r_1,\ldots,r_k;n)$ Ramsey coloring.

For graph coloring problems, solutions are typically closed 