@inproceedings{71f13a1f4f164aaa9a942f14e81981ec,

title = "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 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.",

keywords = "partition refinement, colour refinement, EWI-23837, METIS-300086, IR-88273, Algorithm, Graph Isomorphism",

author = "Christoph Berkholz and P.S. Bonsma and Martin Grohe",

note = "10.1007/978-3-642-40450-4_13 ; 21st Annual European Symposium on Algorithms (ESA 2013), Sophia Antipolis, France ; Conference date: 01-09-2013",

year = "2013",

month = sep,

doi = "10.1007/978-3-642-40450-4_13",

language = "Undefined",

isbn = "978-3-642-40449-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "145--156",

editor = "H.L. Bodlaender and G.F. Italiano",

booktitle = "Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013)",

address = "Germany",

}