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.

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 neighbor 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.

This algorithm keeps refining the current colouring. At some point, before n steps, where n is the number of vertices, it stabilises: $cr^{t}$does not change anymore when t increases. This final colouring is called the stable colouring.

Expressivity

There are simple examples of graphs that are not distinguished by colour refinement. For example, it does not distinguish a cycle of length 6 from a pair of triangles (example V.1 in ). Despite this, the algorithm is very powerful in that a random graph will be identified by the algorithm asymptotically almost surely . Even stronger, it has been shown that as $n$ increases, the proportion of graphs that are not identified by colour refinement decreases exponentially in order $n$.

Complexity

The stable colouring is computable in O((n+m)log n) where n is the number of vertices and m the number of edges. This complexity has been proven to be optimal under reasonable assumptions.