Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00224-016-9686-0 | european symposium on algorithms |
Keywords | Field | DocType |
Graph isomorphism,Colour refinement,Partition refinement,Canonical labelling | Discrete mathematics,Binary logarithm,Graph,Combinatorics,Vertex (geometry),Subroutine,Graph isomorphism,Automorphism,Canonical sequence,Partition refinement,Mathematics | Conference |
Volume | Issue | ISSN |
60 | 4 | 1432-4350 |
Citations | PageRank | References |
9 | 0.51 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Berkholz | 1 | 49 | 7.03 |
| Paul Bonsma | 2 | 287 | 20.46 |
| Martin Grohe | 3 | 2280 | 127.40 |