$n$ let $[n]$ denote the set $\{1,2,\ldots,n\}$. A graph coloring, in $k$ colors, is a pair $(G,\kappa)$ consisting of a simple graph $G=(V,E)$ and a mapping $\kappa\colon E\to[k]$. When $G$ is clear from the context we refer to $\kappa$ as the graph coloring. We typically represent $G=([n],E)$ as a (symmetric) $n\times n$ adjacency matrix, $A$, defined such that $$A_{i,j}=  
    \begin{cases}
       \kappa((i,j)) & \mbox{if } (i,j) \in E\\
          0          & \mbox{otherwise}
    \end{cases}$$

Given a graph coloring $(G,\kappa)$ in $k$ colors with $G=(V,E)$, the set of neighbors of a vertex $u\in V$ in color $c\in [k]$ is $N_c(u) = {\left\{~v  \left|
      \begin{array}{l}(u,v)\in E, \kappa((u,v))=c\end{array}
    \right.     \right\}} $ and the color-$c$ degree of $u$ is $deg_{c}(u) = |N_c(u)|$. The color degree tuple of $u$ is the $k$-tuple $deg(u)={\langle deg_{1}(u),\ldots,deg_{k}(u) \rangle}$. The sub-graph of $G$ on the $c$ colored neighbors of $x\in V$ is the projection of $G$ to vertices in $N_c(x)$ defined by $G^c_x =
(N_c(x),{\left\{~(u,v)\in E  \left|
      \begin{array}{l}u,v\in N_c(x)\end{array}
    \right.     \right\}})$.

For example, take as $G$ the graph coloring depicted by the adjacency matrix in Figure \[embed\_12\_8\_8\] with $u$ the vertex corresponding to the first row in the matrix. Then, $N_1(u) = \{2,3,4,5,6,7,8,9,10,11,12,13\}$, $N_2(u) =
\{14,15,16,17,18,19,20,21\}$, and $N_3(u)=\{22,23,24,25,26,27,28,29\}$. The subgraphs $G^1_u$, $G^2_u$, 