x}))\mid x\in V(\Gamma)\rmulset\right).$$

Here ${\{\!\!\{}
\newcommand{\rmulset}{\}\!\!\}}\cdots \rmulset$ denotes multisets. Thus the color of the next iteration consists of the color of the previous iteration and the multiset of colors obtained by replacing each entry in the tuple with another vertex from the graph. For $k=1$ the definition is slightly different, namely that for $\chi_i(\bar{v})$ the multiset is only taken over vertices $x$ in the neighborhood $N(v)$.

Adding the color of the previous iteration as first entry ensures that the partition induced on $V(\Gamma)$ by $\chi_i$ is finer than (or as fine as) the partition induced by $\chi_{i-1}$. Let $j$ be the least positive integer for which the partition induced by $\chi_{j-1}$ agrees with the partition induced by $\chi_j$, then we define the final coloring $\chi_{\infty}$ to be $\chi_{j-1}$. Since the domain of the $\chi_i$ has size $|V(\Gamma)|^k$, we know that $j\leq |V(\Gamma)|^k$. For fixed $k\in \mathbb{N}$, it is possible to compute the partition of $\chi_{\infty}$ in time $\mathcal{O}(n^{k+1}\log (n))$ [@MR1060782].

To distinguish two non-isomorphic graphs the algorithm is applied on the disjoint union. If in the final coloring the multiset of colors appearing in one graph is different than those appearing in the other graph, then the graphs are not 