of all solutions modulo (weak) isomorphism the task is even more challenging. Often one first attempts to compute all the solutions of the coloring problem, and to then apply one of the available graph isomorphism tools, such as `nauty` [@nauty] to select representatives of their equivalence classes modulo (weak) isomorphism. This is a *generate and test* approach. However, typically the number of solutions is so large that this approach is doomed to fail even though the number of equivalence classes itself is much smaller. The problem is that tools such as `nauty` apply after, and not during, generation. To this end, we follow [@CodishMPS14] where Codish [[*et al.*]{}]{} show that the symmetry breaking approach of [@DBLP:conf/ijcai/CodishMPS13] holds also for graph coloring problems where the adjacency matrix consists of integer variables. This is a *constrain and generate approach*. But, as symmetry breaking does not break all symmetries, it is still necessary to perform some reduction using a tool like `nauty`.[^3] This form of symmetry breaking is an important component in our methodology.

**[@DBLP:conf/ijcai/CodishMPS13].** \[def:SBlexStar\] Let $A$ be an $n\times n$ adjacency matrix. Then, $$\label{eq:symbreak}
 {\textsf{sb}}^*_\ell(A) = \bigwedge{\left\{~A_{i}\preceq_{\{i,j\}}A_{j}  \left|
      \begin{array}{l}i<j\end{array}
    \right.     \right\}}$$ where $A_{i}\preceq_{\{i,j\}}A_{j}$ denotes the lexicographic order between the $i^{th}$ and 