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.

History

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^(v) = \left(cr^t(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

This algorithm does not distinguish a cycle of length 6 from a pair of triangles (example V.1 in ).

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 for some class of graphs.

References

{{ci, date=September 2022

Graph algorithms
Isomorphism theorems