A Classification of Long-Refinement Graphs for Colour Refinement
Abstract
The Colour Refinement algorithm is a classical procedure to detect symmetries in graphs, whose most prominent application is in graph-isomorphism tests. The algorithm and its generalisation, the Weisfeiler–Leman algorithm, evaluate local information to compute a colouring for the vertices in an iterative fashion. Different final colours of two vertices certify that no isomorphism can map one onto the other.
Fields of Study & Subjects
Color Science and Applications
Color perception and design
Categorization
perception
and language
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 388–407
- Publication date
- 1 January 2026
- Language
- EN