Highlights:
- A complete classification of long-refinement graphs up to degree 4 has been achieved.
- Findings confirm that the theoretical upper bound of Colour Refinement iterations is tight.
- Research extends earlier work by Kiefer and McKay on low-degree long-refinement graphs.
- New structural insights reveal compact string representations of low-degree graphs.
TLDR:
Sandra Kiefer and T. Devini de Mel present a comprehensive classification of long-refinement graphs, closing a longstanding question in Colour Refinement complexity and providing new structural insights into graph symmetries.
In a significant advancement for theoretical computer science and discrete mathematics, researchers Sandra Kiefer (https://arxiv.org/search/cs?searchtype=author&query=Kiefer,+S) and T. Devini de Mel (https://arxiv.org/search/cs?searchtype=author&query=de+Mel,+T+D) have published a landmark paper titled *A Classification of Long-Refinement Graphs for Colour Refinement* on arXiv (arXiv:2510.20802). Their work provides the first complete characterisation of long-refinement graphs, a class of graphs that require the maximum number of Colour Refinement iterations to complete—a core concept underlying graph isomorphism testing.
The Colour Refinement algorithm, widely used in algorithms that test graph isomorphism, iteratively applies a vertex-colouring process until no further refinement is possible. This study resolves a longstanding question about whether graphs exist that reach the theoretical maximal number of refinement steps. Previous researchers, Kiefer and McKay, had shown that such infinite families of long-refinement graphs exist for degrees 2 and 3. Building upon this foundation, Kiefer and de Mel now demonstrate that, with a single known exception, these are the only such families with a maximum vertex degree of three—and they extend the classification to include degree-four graphs.
Employing an innovative reverse-engineering approach, the team proved that all low-degree long-refinement graphs can be described as compact strings. This discovery not only simplifies the representation of such graphs but also reveals new structural symmetries within them. Since long-refinement graphs are mathematically closed under edge complementation, the classification of low-degree graphs inherently applies to high-degree cases as well. Notably, the authors resolve another open problem by proving that graphs distinguishable solely in the final iteration of Colour Refinement cannot exist. These findings deepen our understanding of the computational complexity of symmetry detection and may have far-reaching implications for graph-based algorithms in cryptography, machine learning, and network analysis.
Source:
Source:
Original research paper: Sandra Kiefer and T. Devini de Mel, ‘A Classification of Long-Refinement Graphs for Colour Refinement’, arXiv:2510.20802 [cs.DM], https://doi.org/10.48550/arXiv.2510.20802.