Tight lower and upper bounds for the complexity of canonical colour refinement

Abstract. An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neigh-bourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subrou-tine 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.