Abstract
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.
| Original language | Undefined |
|---|---|
| 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 |
| Publisher | Springer |
| Pages | 145-156 |
| Number of pages | 12 |
| ISBN (Print) | 978-3-642-40449-8 |
| DOIs | |
| Publication status | Published - Sep 2013 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Volume | 8125 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Keywords
- partition refinement
- colour refinement
- EWI-23837
- METIS-300086
- IR-88273
- Algorithm
- Graph Isomorphism
Cite this
Berkholz, C., Bonsma, P. S., & Grohe, M. (2013). Tight lower and upper bounds for the complexity of canonical colour refinement. In H. L. Bodlaender, & G. F. Italiano (Eds.), Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013) (pp. 145-156). (Lecture Notes in Computer Science; Vol. 8125). Berlin: Springer. https://doi.org/10.1007/978-3-642-40450-4_13