2026-07-20T14:36:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22900 2025-10-02T13:36:54Z ddc:004 open_access

Canonical Labeling of Sparse Random Graphs Verbitsky, Oleg Zhukovskii, Maksim Graph isomorphism random graphs canonical labeling color refinement We show that if p = O(1/n), then the Erdős-Rényi random graph G(n,p) with high probability admits a canonical labeling computable in time O(nlog n). Combined with the previous results on the canonization of random graphs, this implies that G(n,p) with high probability admits a polynomial-time canonical labeling whatever the edge probability function p. Our algorithm combines the standard color refinement routine with simple post-processing based on the classical linear-time tree canonization. Noteworthy, our analysis of how well color refinement performs in this setting allows us to complete the description of the automorphism group of the 2-core of G(n,p). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oleg Verbitsky and Maksim Zhukovskii 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.75 urn:nbn:de:0030-drops-229003 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.75 eng https://creativecommons.org/licenses/by/4.0/legalcode