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.
|Title of host publication||Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013)|
|Editors||H.L. Bodlaender, G.F. Italiano|
|Place of Publication||Berlin|
|Number of pages||12|
|Publication status||Published - Sep 2013|
|Name||Lecture Notes in Computer Science|
- partition refinement
- colour refinement
- Graph Isomorphism