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.
The algorithm takes as an input a graph
In each iteration, we define a sequence of vertex colourings
This algorithm keeps refining the current colouring.
Colour refinement can be used as a subroutine for an important computational problem: graph isomorphism.
Informally, this means that the two graphs are the same up to relabelling of vertices.
Run colour refinement on both graphs.
If the stable colourings produced are different we know that the two graphs are not isomorphic.
However, it could be that the same stable colouring is produced despite the two graphs not being isomorphic; see below.
vertex graph as input, a stable colouring is produced after at most
Conversely, there exist graphs where this bound is realised.
[3] This complexity has been proven to be optimal under reasonable assumptions.
are distinguished by colour refinement if the algorithm yields a different output on
There are simple examples of graphs that are not distinguished by colour refinement.
increases, the proportion of graphs that are not identified by colour refinement decreases exponentially in order
[7] The expressivity of colour refinement also has a logical characterisation: two graphs can be distinguished by colour refinement if and only if they can be distinguished by the two variable fragment of first order logic with counting.