DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.114

Canonical Labelling of Random Regular Graphs

Authors: Mikhail Isaev, Tamás Makai, Brendan D. McKay, Paweł Prałat, Jane Tan, and Maksim Zhukovskii

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Mikhail Isaev, Tamás Makai, Brendan D. McKay, Paweł Prałat, Jane Tan, and Maksim Zhukovskii. Canonical Labelling of Random Regular Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 114:1-114:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{isaev_et_al:LIPIcs.ICALP.2026.114,
  author =	{Isaev, Mikhail and Makai, Tam\'{a}s and McKay, Brendan D. and Pra{\l}at, Pawe{\l} and Tan, Jane and Zhukovskii, Maksim},
  title =	{{Canonical Labelling of Random Regular Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{114:1--114:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.114},
  URN =		{urn:nbn:de:0030-drops-265039},
  doi =		{10.4230/LIPIcs.ICALP.2026.114},
  annote =	{Keywords: random graphs, regular graphs, colour refinement, canonical labelling, graph isomorphism}
}

@InProceedings{isaev_et_al:LIPIcs.ICALP.2026.114,
  author =	{Isaev, Mikhail and Makai, Tam\'{a}s and McKay, Brendan D. and Pra{\l}at, Pawe{\l} and Tan, Jane and Zhukovskii, Maksim},
  title =	{{Canonical Labelling of Random Regular Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{114:1--114:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.114},
  URN =		{urn:nbn:de:0030-drops-265039},
  doi =		{10.4230/LIPIcs.ICALP.2026.114},
  annote =	{Keywords: random graphs, regular graphs, colour refinement, canonical labelling, graph isomorphism}
}

Search Results

Documents authored by Isaev, Mikhail

Canonical Labelling of Random Regular Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message