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

The algorithm takes as an input a graph $G$ with $n$ vertices. It proceeds in iterations and in each iteration we produce a new colouring of the vertices. Formally a "colouring" is a function from the vertices of this graph into some set (of "colours"). In each iteration, we define a sequence of vertex colourings $\lambda _{i}$ as follows:

• $\lambda _{0}$is the initial colouring. If the graph is unlabeled, the initial colouring assigns a trivial colour $\lambda _{0}(v)$ to each vertex $v$. If the graph is labelled, $\lambda _{0}$ is the label of vertex $v$.
• For all vertices $v$, we set $\lambda _{i+1}=\left(\lambda _{i}(v),\{\{\lambda _{i}(w)\mid w{\text{ is a neighbor of }}v\}\}\right)$.

In other words, the new colour of the vertex $v$ is the pair formed from the previous colour and the multiset of the colours of its neighbours. This algorithm keeps refining the current colouring. At some point it stabilises, i.e., $\lambda _{i+1}=\lambda _{i}$. 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.