Id: arxiv/2602.17567 Url: https://arxiv.org/abs/2602.17567 Tags: math.CO, cs.DM, math.PR Score: 0 Title: Canonical labelling of random regular graphs Domain: math.CO Source: arxiv Authors: Mikhail Isaev, Tamás Makai, Brendan McKay, Pawel Pralat, Jane Tan, Maksim Zhukovskii Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-19 Page: https://delphi.science/r/arxiv/2602.17567 We prove that whenever $d=d(n)\to\infty$ and $n-d\to\infty$ as $n\to\infty$, then with high probability for any non-trivial initial colouring, the colour refinement algorithm distinguishes all vertices of the random regular graph $\mathcal{G}_{n,d}$. This, in particular, implies that with high probability $\mathcal{G}_{n,d}$ admits a canonical labelling computable in time $O(\min\{n^ω,nd^2+nd\log n\})$, where $ω<2.372$ is the matrix multiplication exponent.