mlsanityData to 7 Oct 2026

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

arXiv 1509.08251 ↗First posted 28 Sep 2015cs.DS cs.CCcited by 16

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Sep 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 2; 2024: 1; 2025: 1; 2026: 5.

16 papers.

Sort:

  1. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  2. 2021The Logic of Graph Neural Networkscited by 84
  3. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  4. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  5. 2023WL meet VCcited by 30
  6. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  7. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  8. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  9. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  10. 2022Gradual Weisfeiler-Leman: Slow and Steady Wins the Racecited by 5
  11. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  12. 2025From Small to Large: A Graph Convolutional Network Approach for Solving Assortment Optimization Problemscited by 0
4 more
  1. 2026Exact Instance Compression for Convex Empirical Risk Minimization via Color Refinementcited by 0
  2. 2026Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networkscited by 0
  3. 2026Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUscited by 0
  4. 2026M-Fibration Theory with Applications to Weighted Graphscited by 0