underlying our approach is that when the combinatorial problem at hand is too hard, then possibly solving an abstraction of the problem is easier. In this case, a solution of the abstract problem can be used to facilitate the search for a solution of the original problem.

\[def:dm\] Let $A$ be a graph coloring on $n$ vertices with $k$ colors. The *degree matrix* of $A$, denoted $dm(A)$ is an $n\times k$ matrix, $M$ such that $M_{i,j} = deg_j(i)$ is the degree of vertex $i$ in color $j$.

[r]{}[.33]{}

Figure \[fig:dm\] illustrates the degree matrix of the graph coloring given as Figure \[embed\_12\_8\_8\]. The three columns correspond to the three colors and the 29 rows to the 29 vertices. The degree matrix consists of 29 identical rows as the corresponding graph coloring is ${\langle 12,8,8 \rangle}$ regular.

A degree matrix $M$ represents the set of graphs $A$ such that $dm(A)=M$. Due to properties of weak-isomorphism (vertices as well as colors can be reordered) we can exchange both rows and columns of a degree matrix without changing the set of graphs it represents. In the rest of our construction we adopt a representation in which the rows and columns of a degree 