Colour refinement algorithm

In graph theory and theoretical computer science, the colour refinement algorithm also known as the naive vertex classification, or the 1-dimensional version of the Weisfeiler-Leman algorithm, is a routine used for testing whether two graphs are isomorphic or not.

Description

We define a sequence of vertex colourings $cr^{t}$ defined as follows:

• $cr^{0}$is the initial colouring. If the graph is unlabeled, the initial colouring assigns a trivial color $cr^{0}(v)$ to each vertex $v$. If the graph is labeled, $cr^{0}(v)$ is the label of vertex $v$.
• For all vertices $v$, we set $cr^{t+1}(v)=\left(cr^{t}(v),\{\{cr^{t}(w)\mid w{\text{ is a neightbor of }}v\}\}\right)$. In other words, the new color of the vertex $v$ is the pair formed from the previous color and the multiset of the colors of its neighbors.