under permutations of vertices and of colors. Restricting the search space for a solution modulo such permutations is crucial when trying to solve hard graph coloring problems. It is standard practice to formalize this in terms of graph (coloring) isomorphism.

Let $G=(V,E)$ be a graph (coloring) with $V=[n]$ and let $\pi$ be a permutation on $[n]$. Then $\pi(G) = (V,{\left\{~ (\pi(x),\pi(y))  \left|
      \begin{array}{l} (x,y)
  \in E\end{array}
    \right.     \right\}})$. Permutations act on adjacency matrices in the natural way: If $A$ is the adjacency matrix of a graph $G$, then $\pi(A)$ is the adjacency matrix of $\pi(G)$ and $\pi(A)$ is obtained by simultaneously permuting with $\pi$ both rows and columns of $A$.

\[def:weak\_iso\] Let $(G,{\kappa_1})$ and $(H,{\kappa_2})$ be $k$-color graph colorings with $G=([n],E_1)$ and $H=([n],E_2)$. We say that $(G,{\kappa_1})$ and $(H,{\kappa_2})$ are weakly isomorphic, denoted $(G,{\kappa_1})\approx(H,{\kappa_2})$ if there exist permutations $\pi \colon [n] \to [n]$ and $\sigma \colon [k]
 \to [k]$ such that $(u,v) \in E_1 \iff (\pi(u),\pi(v)) \in E_2$ and $\kappa_1((u,v)) = \sigma(\kappa_2((\pi(u), \pi(v))))$. We denote such a weak isomorphism: $(G,{\kappa_1})\approx_{\pi,\sigma}(H,{\kappa_2})$. When $\sigma$ is the identity permutation, we say that $(G,{\kappa_1})$ and $(H,{\kappa_2})$ are isomorphic.

The following lemma emphasizes the importance of weak graph isomorphism as it relates to Ramsey numbers. 