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  defined as follows:

 is the initial colouring. If the graph is unlabeled, the initial colouring assigns a trivial color  to each vertex . If the graph is labeled,  is the label of vertex . For all vertices , we set . In other words, the new color of the vertex  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: 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

Graph algorithms
Isomorphism theorems