Long-Refinement Graphs

The Colour Refinement algorithm is a classical procedure to detect symmetries in graphs, whose most prominent application is in graph-isomorphism tests. The algorithm evaluates local information to compute a colouring for the vertices in an iterative fashion.

The number of iterations that the algorithm takes to terminate is its central complexity parameter. For a long time, it was an open question whether graphs that take the maximum theoretically possible number of Colour Refinement iterations actually exist. My talk will give an overview of the history of long-refinement graphs, as well as a report on recent results.

Together with Brendan McKay I proved the existence of infinite families of such long-refinement graphs with degrees 2 and 3, thereby showing that the trivial upper bound on the iteration number of Colour Refinement is tight. Recently, via reverse-engineering, T. Devini de Mel and I obtained a complete characterization of the long-refinement graphs with small (or, equivalently, large) degrees. This yields that, with one exception, the aforementioned families are the only long-refinement graphs with maximum degree at most 3, and hence that all long-refinement graphs with degree 2 and 3 can be described via compact strings over a very small alphabet.

The work with McKay initiated a search for long-refinement graphs that are only distinguished in the last iteration of Colour Refinement before termination. In the talk, I will present a simple argument to show that such graphs do not exist.