{"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","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-19","reactions":{}}