Canonical labelling of random regular graphs

Abstract

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^{\ddot{I}}‰,n{d}^2+nd\log n\})$, where $\ddot{I}‰<2.372$ is the matrix multiplication exponent.