2026-09-08T02:22:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26503 2026-09-05T19:45:51Z ddc:004 open_access

Canonical Labelling of Random Regular Graphs Isaev, Mikhail Makai, Tamás McKay, Brendan D. Prałat, Paweł Tan, Jane Zhukovskii, Maksim random graphs regular graphs colour refinement canonical labelling graph isomorphism We prove that whenever d = d(n) → ∞ and n-d → ∞ as n → ∞, then with high probability for any non-trivial initial colouring, the colour refinement algorithm distinguishes all vertices of the random regular graph 𝒢_{n,d}. This, in particular, implies that with high probability 𝒢_{n,d} admits a canonical labelling computable in time O(min{n^ω, nd²+ndlog n}), where ω < 2.372 is the matrix multiplication exponent. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikhail Isaev and Tamás Makai and Brendan D. McKay and Paweł Prałat and Jane Tan and Maksim Zhukovskii 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.114 urn:nbn:de:0030-drops-265039 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.114 eng https://creativecommons.org/licenses/by/4.0/legalcode