  An assignment of colours to the vertices of a graph is stable if any two
vertices of the same colour have identically coloured neighbourhoods. The goal
of colour refinement is to find a stable colouring that uses a minimum number
of colours. This is a widely used subroutine for graph isomorphism testing
algorithms, since any automorphism needs to be colour preserving. We give an
$O((m+n)\log n)$ algorithm for finding a canonical version of such a stable
colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster
algorithm is possible, under some modest assumptions about the type of
algorithm, which captures all known colour refinement algorithms.
