Combinatorial Theory Seminar

Colour Refinement is a combinatorial method that distinguishes vertices in graphs based on their local neighborhood structure. By encoding these local properties into vertex colours that are refined iteratively, the process eventually stabilises into a final colouring which serves as an isomorphism test on a large class of graphs.

The central complexity parameter of the algorithm is the number of iterations required to reach stabilisation. For $n$-vertex graphs, the upper bound is $n−1$. We call graphs that attain this maximum long-refinement graphs. Their final colourings are discrete, meaning every vertex is uniquely identified by its colour.  For a long time, it was not clear whether such graphs actually exist. My talk provides an overview of the history of this graph class and reports on recent work towards a full characterisation of it.

By restricting our scope to graphs with small degrees, we have constructed infinite families of long-refinement graphs. Furthermore, by reverse-engineering connections between colour classes, we obtained a complete classification of long-refinement graphs with small (or, equivalently, large) degrees. This analysis offers deep insights into the dynamics of the refinement process, revealing that all long-refinement graphs with maximum degree 3 can be described by compact strings over a remarkably small alphabet.

The talk is based on collaborations with Brendan D. McKay and T. Devini de Mel.