Canonical Labeling of Sparse Random Graphs

Verbitsky, Oleg; Zhukovskii, Maksim

doi:10.4230/LIPIcs.STACS.2025.75

Canonical Labeling of Sparse Random Graphs

Oleg Verbitsky

Institut für Informatik, Humboldt-Universität zu Berlin, Germany Maksim Zhukovskii

School of Computer Science, University of Sheffield, UK

Abstract

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(n\log 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)$ .

Keywords and phrases:

Graph isomorphism, random graphs, canonical labeling, color refinement

Funding:

Oleg Verbitsky: Supported by DFG grant KO 1053/8–2. On leave from the IAPMM, Lviv, Ukraine.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Random graphs ; Mathematics of computing

\rightarrow

Graph algorithms

Related Version:

Full Version: https://arxiv.org/abs/2409.18109 [33]

Acknowledgements:

The authors would like to thank Michael Krivelevich for helpful discussions.

DOI:

10.4230/LIPIcs.STACS.2025.75

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

On an $n$ -vertex input graph $G$ , a canonical labeling algorithm computes a bijection $\lambda_{G}:V(G)\rightarrow\{1,\ldots,n\}$ such that if another graph $G^{\prime}$ is isomorphic to $G$ , then the isomorphic images of $G$ and $G^{\prime}$ under respective permutations $\lambda_{G}$ and $\lambda_{G^{\prime}}$ are equal. Given the labelings $\lambda_{G}$ and $\lambda_{G^{\prime}}$ , it takes linear time to check whether $G$ and $G^{\prime}$ are isomorphic. The existence of polynomial-time algorithms for testing isomorphism of two given graphs and, in particular, for producing a canonical labeling remain open. Babai’s breakthrough quasi-polynomial algorithm for testing graph isomorphism [7] was subsequently extended to a canonical labeling algorithm of the same time complexity [8]. In the present paper, we address the canonical labeling problem for the Erdős-Rényi (or binomial) random graph $G(n,p)$ . Recall that the vertex set of $G(n,p)$ is $\{1,\ldots,n\}$ , and each pair of vertices is adjacent with probability $p=p(n)$ , independently of the other pairs.

Babai, Erdős, and Selkow [5] proved that the simple algorithmic routine known as color refinement (CR for brevity) with high probability produces a discrete coloring of the vertices of $G(n,1/2)$ , that is, a coloring where the vertex colors are pairwise different. Since the vertex colors are isomorphism-invariant, this yields a canonical labeling of $G(n,1/2)$ by numbering the color names in the lexicographic order. Here and throughout, we say that an event happens for $G(n,p)$ with high probability (whp for brevity) if the probability of this event tends to 1 as $n\to\infty$ . The result of [5] has a fundamental meaning: almost all graphs admit an easily computable canonical labeling and, hence, the graph isomorphism problem has low average-case complexity.

The argument of [5] can be extended to show [14, Theorem 3.17] that the CR coloring of $G(n,p)$ is whp discrete for all $n^{-1/5}\ln n\ll p\leq 1/2$ . Note that it is enough to consider the case of $p\leq 1/2$ since $G(n,1-p)$ has the same distribution as the complement of $G(n,p)$ . Remarkably, the algorithm of Babai, Erdős, and Selkow performs only a bounded number of color refinement steps and, due to this, works in linear time.

A different algorithm suggested by Bollobás [12] works in polynomial time and whp produces a canonical labeling of $G(n,p)$ in a much sparser regime, namely when $\frac{(1+\delta)\ln n}{n}\leq p\leq 2n^{-11/12}$ for any positive constant $\delta$ . The next improvement was obtained by Czajka and Pandurangan [16] who proved that, in a bounded number of rounds, CR yields a discrete coloring of $G(n,p)$ whp when $\frac{\ln^{4}n}{n\ln\ln n}\ll p\leq\frac{1}{2}$ . Finally, Linial and Mosheiff [27] designed a polynomial time algorithm for canonical labeling of $G(n,p)$ when $\frac{1}{n}\ll p\leq\frac{1}{2}$ . As shown by Gaudio, Rácz, and Sridhar [21], in the subdiapason $p\geq\frac{(1+\delta)\ln n}{n}$ for any fixed $\delta>0$ , a canonical labeling can still be provided by CR in a bounded number of rounds.

The decades-long line of research summarized above leaves open the question whether a random graph $G(n,p)$ admits efficient canonization in the regime $p=O(1/n)$ . Note that the case of $p=o(1/n)$ is easy. Indeed, as long as $pn=1-\omega(n^{-1/3})$ , whp $G(n,p)$ is a vertex-disjoint union of trees and unicyclic graphs (i.e., connected graphs containing exactly one cycle). Canonization of such graphs is tractable due to the classical linear-time canonical labeling algorithms for trees [1] and even planar graphs (see [6] for a survey of the early work on graph isomorphism covering these graph classes). Thus, efficient canonization remains unknown for all $p=p(n)$ such that, for some $C>0$ and all $n$ , $1-Cn^{-1/3}\leq pn\leq C$ (even though $G(n,p)$ stays planar with a non-negligible probability as long as $pn=1+O(n^{-1/3})$ ; see [32]). Our first result closes this gap.

Theorem 1.

If $p=O(1/n)$ , then $G(n,p)$ whp admits a canonical labeling computable in time $O(n\log n)$ .

Table 1: Canonical labeling algorithms for random graphs in the full-scale Erdős-Rényi evolutional model

G(n,p)

.

Edge probability	Algorithm
$p=\frac{1}{2}$	Babai, Erdős, and Selkow [5]^∗
$n^{-1/5}\ln n\ll p\leq 1/2$	Bollobás [14]^∗
$\frac{(1+\delta)\ln n}{n}\leq p\leq 2n^{-11/12}$	Bollobás [12]
$\frac{\ln^{4}n}{n\ln\ln n}\ll p\leq\frac{1}{2}$	Czajka and Pandurangan [16]^∗
$\frac{(1+\delta)\ln n}{n}\leq p\ll n^{-5/6}$	Gaudio, Rácz, and Sridhar [21]^∗
$\frac{1}{n}\ll p\leq\frac{1}{2}$	Linial and Mosheiff [27]
$p=O(\frac{1}{n})$	this paper

The development of canonical labeling algorithms for $G(n,p)$ is summarized in Table 1. The sources marked by ^∗ show that canonical labeling in the corresponding range can be obtained by CR in a constant number of refinement rounds. An inspection of the other algorithms reveals that all of them can be implemented as a combination of the 2-WL (2-dimensional Weisfeiler-Leman) algorithm [34] with tree canonization. The 2-WL is an extension of CR which computes a canonical coloring of pairs of vertices. Thus, in these cases, canonical labeling can be obtained in time $O(n^{3}\log n)$ , matching the running time bound for 2-WL (see [23]). If $p=O(1/n)$ , the running time is actually $O(n\log n)$ because our algorithm, as discussed below, uses CR along with simple pre- and post-processing.

A simple argument shows that Theorem 1, combined with the previous results, implies that the Erdős-Rényi random graph $G(n,p)$ whp admits an efficiently computable canonical labeling whatever the edge probability function $p(n)$ .

Corollary 2.

There exists a polynomial time algorithm that, for any function $p=p(n)$ with values in $[0,1]$ , whp produces a canonical labeling of $G(n,p)$ .

We now recall some highlights of the evolution of the random graph. Erdős and Rényi [19] proved their spectacular result that when $p$ passes a certain threshold around $1/n$ , then the size of the largest connected component in $G(n,p)$ rapidly grows from $\Theta(\log n)$ to $\Theta(n)$ . A systematic study of the structure of connected components in the random graph when $p$ is around the critical value $1/n$ was initiated in the influential paper of Bollobás [13]. For more details about the phase transition, see, e.g., [24, Chapter 5].

A connected graph is called complex, if it has more than one cycle. The union of all complex components of a graph $G$ will be called the complex part of $G$ , and the union of the other components will be referred to as the simple part. As we already mentioned, if $pn=1-\omega(n^{-1/3})$ then the complex part of $G(n,p)$ is whp empty. This is the so-called subcritical phase. In the critical phase, when $pn=1\pm O(n^{-1/3})$ , the complex part of $G(n,p)$ whp has size $O_{P}(n^{2/3})$ and its structure is thoroughly described in [29, 30]. Here and below, for a sequence of random variables $\xi_{n}$ and a sequence of reals $a_{n}$ we write $\xi_{n}=O_{P}(a_{n})$ if the sequence $\xi_{n}/a_{n}$ is stochastically bounded¹¹1I.e. for every $\varepsilon>0$ , there exists $C>0$ and $n_{0}$ such that $\mathbb{P}(|\xi_{n}/a_{n}|>C)<\varepsilon$ for all $n\geq n_{0}$ .. Finally, in the supercritical phase, when $pn=1+\omega(n^{-1/3})$ , whp $G(n,p)$ contains a unique complex connected component and this component has size $\Theta(n^{2}(p-1/n))$ . In particular, when $p=O(1/n)$ and $p>(1+\delta)/n$ for a constant $\delta>0$ (we refer to this case as strictly supercritical regime), whp this component has linear size $\Omega(n)$ . It is called the giant component as all the other connected components have size $O(\log n)$ .

In general, the simple part of a graph $G$ is easily canonizable by the known techniques, which reduces our problem to finding a canonical labeling for the complex part of $G$ . Furthermore, recall that the 2-core of a graph $H$ , which we will for brevity call just core and denote by $\operatorname{core}(H)$ , is the maximal subgraph of $H$ that does not have vertices of degree 1. Equivalently, $\operatorname{core}(H)$ can be defined as the subgraph of $H$ obtained by iteratively pruning all vertices in $H$ that have degree at most 1 until there are no more such vertices. Thus, if $H$ is the (non-empty) complex part of $G$ , then $H$ consists of $\operatorname{core}(H)$ and some (possibly empty) rooted trees planted at the vertices of the core. It follows that if we manage to canonically label the vertices of $\operatorname{core}(H)$ , then this labeling easily extends to a canonical labeling of the entire graph $G$ .

Suppose that CR is run on $H$ . In the most favorable case, it would output a vertex coloring discrete on $\operatorname{core}(H)$ . It turns out that, though not exactly true, this is indeed the case to a very large extent.

Theorem 3.

Let $G_{n}=G(n,p)$ and assume that $p=O(1/n)$ . Let $\mathsf{H}_{n}$ denote the complex part of $G_{n}$ and $\mathsf{C}_{n}=\operatorname{core}(\mathsf{H}_{n})$ . When CR is run on $\mathsf{H}_{n}$ , then

1.

CR assigns individual colors to all but $O_{P}(1)$ vertices in $\mathsf{C}_{n}$ ;
2.

the other color classes whp have size 2;
3.

whp, every such color class is an orbit of the automorphism group $\operatorname{Aut}(\mathsf{H}_{n})$ consisting of two vertices with degree 2 in $\mathsf{C}_{n}$ .

$\blacktriangleright$ Remark 4.

From our proofs it is easy to derive that, when $np=1+o(1)$ , then CR distinguishes between all vertices of $\mathsf{C}_{n}$ whp.

Theorem 3 allows us to obtain an efficient canonical labeling algorithm for $G(n,p)$ , as stated in Theorem 1, by combining CR with simple post-processing whose most essential part is invoking the linear-time tree canonization. Another consequence of Theorem 3 is that CR alone is powerful enough to solve the standard version of the graph isomorphism problem for the complex part of $G(n,p)$ . Specifically, we say that a graph $H$ is identifiable by CR if CR distinguishes $H$ from any non-isomorphic graph $H^{\prime}$ (in the sense that CR outputs different multisets of vertex colors on inputs $H$ and $H^{\prime}$ ). It is not hard to see that $H$ is identifiable by CR whenever the CR coloring of $H$ is discrete. Fortunately, the properties of the CR coloring ensured by Theorem 3 are still sufficient for CR-identifiability.

Corollary 5.

Under the assumption of Theorem 3,

1.

$\mathsf{H}_{n}$ is whp identifiable by CR and, consequently,
2.

whp, $G_{n}$ is identifiable by CR exactly when the simple part of $G_{n}$ is identifiable.

The CR-identifiability of the simple part of a graph admits an explicit, efficiently verifiable characterization, which we give in Theorem 14. This characterization can be used to show that the random graph $G_{n}$ is identifiable by CR with probability asymptotically bounded away from 0 and 1.

Our techniques for proving Theorems 1 and 3 can also be used for deriving a structural information about the automorphisms of a random graph. As proved by Erdős and Rényi [20] and by Wright [35], $G(n,p)$ for $p\leq 1/2$ is asymmetric, i.e., has no non-identity automorphism, if $np-\ln n\to\infty$ as $n\to\infty$ . This result is best possible because if, $np-\ln n\leq\gamma$ for some constant $\gamma>0$ , then the random graph has at least 2 isolated vertices with non-vanishing probability. It is noteworthy that the asymmetry of $G(n,p)$ in the regime $p\geq\frac{(1+\delta)\ln n}{n}$ can be certified by the fact that CR coloring of $G(n,p)$ is discrete due to the aforementioned result of Gaudio, Rácz, and Sridhar [21]. In the diapason of $p$ forcing $G(n,p)$ to be disconnected, the action of the automorphism group can be easily understood on the simple part and on the tree-like pieces of the complex part, and full attention should actually be given to the core of the complex part. Theorem 3 provides a pretty much precise information about the action of $\operatorname{Aut}(G_{n})$ on $\mathsf{C}_{n}$ . More subtle questions arise if, instead of considering the action of $\operatorname{Aut}(G_{n})$ on $\mathsf{C}_{n}$ , we want to understand the automorphisms of $\mathsf{C}_{n}$ itself. It is quite remarkable that the CR algorithm, applied to $\mathsf{C}_{n}$ rather than to $\mathsf{H}_{n}$ , can serve as a sharp instrument for tackling this problem (and, in fact, the proof of Theorem 3 is based on an analysis of the output of CR on $\mathsf{C}_{n}$ ).

We begin with describing simple types of potential automorphisms of $\mathsf{C}_{n}$ (with the intention of showing that, whp, all automorphism of $\mathsf{C}_{n}$ are actually of this kind). If a vertex $x$ has degree 2 in $\mathsf{C}_{n}$ , then it belongs to a (unique) path from a vertex $s$ of degree at least 3 to a vertex $t$ of degree at least 3 with all intermediate vertices having degree 2. We call such a path in $\mathsf{C}_{n}$ pendant. It is possible that $s=t$ , and in this case we speak of a pendant cycle. Clearly, the reflection of a pendant cycle fixing its unique vertex of degree more than 2 is an automorphism of $\mathsf{C}_{n}$ . Furthermore, call two pendant paths transposable if they have the same length and share the endvertices. Note that $\mathsf{C}_{n}$ has an automorphism transposing such paths (and fixing their endvertices). Let $A_{1}$ denote the set of the automorphisms provided by pendant cycles, and let $A_{2}$ be the set of the automorphisms provided by transposable pairs of pendant paths. Moreover, $\mathsf{C}_{n}$ can have a connected component consisting of two vertices of degree 3 and three pendant paths of pairwise different lengths between these vertices. Such a component has a single non-trivial automorphism, which contributes in $\operatorname{Aut}(\mathsf{C}_{n})$ . The set of such automorphisms of $\mathsf{C}_{n}$ will be denoted by $A_{3}$ .

Recall that an elementary abelian 2-group is a group in which all non-identity elements have order 2 or, equivalently, a group isomorphic to the group $(\mathbb{Z}_{2})^{k}$ for some $k$ .

Theorem 6.

Let $G_{n}=G(n,p)$ and assume that $p=O(1/n)$ . Let $\mathsf{C}_{n}$ be the core of the complex part of $G_{n}$ .

1.

The order of $\operatorname{Aut}(\mathsf{C}_{n})$ is stochastically bounded, i.e., $|\operatorname{Aut}(\mathsf{C}_{n})|=O_{P}(1)$ .
2.

Whp, $\operatorname{Aut}(\mathsf{C}_{n})$ is an elementary abelian 2-group. Moreover, $A_{1}\cup A_{2}\cup A_{3}$ is a minimum generating set of $\operatorname{Aut}(\mathsf{C}_{n})$ .²²2Consequently, whp $\mathsf{C}_{n}$ contains neither a triple of pairwise transposable paths, nor two isomorphic components with an automorphism in $A_{3}$ , nor a cyclic component with a single chord between diametrically opposite vertices. Moreover, whp no two pendant cycles in $\mathsf{C}_{n}$ share a vertex.
3.
In addition,
1. (a)
  
  if $pn\geq 1+\delta$ for a constant $\delta>0$ , then both $A_{1}$ and $A_{2}$ are non-empty with non-negligible probability, while $A_{3}=\varnothing$ whp.
2. (b)
  
  If $pn=1+o(1)$ and $pn=1+\omega(n^{-1/3})$ , then $A_{1}\neq\varnothing$ with non-negligible probability, while $A_{2}=A_{3}=\varnothing$ whp.
3. (c)
  
  If $pn=1\pm O(n^{-1/3})$ , then both $A_{1}$ and $A_{3}$ are non-empty with non-negligible probability, while $A_{2}=\varnothing$ whp.

This theorem makes a final step in the study of the automorphisms group of a random graph. Recall that $\mathsf{H}_{n}$ is whp empty when $np=1-\omega(n^{-1/3})$ and that $G(n,p)$ is connected and asymmetric when $np=\ln n+\omega(1)$ . We, therefore, focus on the intermediate diapason. If $np\to\infty$ as $n\to\infty$ , then the core of the giant component of $G(n,p)$ is whp still asymmetric, as proved independently by Łuczak [28] and Linial and Mosheiff [27]. Moreover, Łuczak described the automorphisms group of the core of the giant component of $G(n,p)$ when $np>\gamma$ for a large enough constant $\gamma$ , and obtained an analogue of Theorem 6 for this case; see [28, Theorem 4]. Our Theorem 6 not only extends [28, Theorem 4] to the full range of $p=O(1/n)$ but also refines this result even for $np>\gamma$ by showing that $\operatorname{Aut}(\mathsf{C}_{n})$ is actually an elementary 2-group. Another interesting observation is that some automorphisms of the core do not extend to automorphisms of the entire $G(n,p)$ . Indeed, if $np=1+o(1)$ , then whp $\operatorname{Aut}(G(n,p))$ acts trivially on the core; see Remark 4.

Related work.

As we already mentioned, Theorem 1 combined with the previous results on canonical labeling of $G(n,p)$ for $1/n\ll p\leq 1/2$ implies the existence of a polynomial-time canonical labeling algorithm succeeding on $G(n,p)$ whp for an arbitrary edge probability function $p=p(n)$ . In this form, this result has been independently obtained by Michael Anastos, Matthew Kwan, and Benjamin Moore [2]. Another result in their paper describes the action of $\operatorname{Aut}(G(n,p))$ on the core of $G(n,p)$ , which follows also from our Theorem 3 and the results of Łuczak [28] and Linial and Mosheiff [27]. The techniques used in [2] and in our paper are completely different, though both proofs rely on color refinement. The two approaches have their own advantages. The method developed in [2] is used there also to show that color refinement is helpful for canonical labeling of the random graph when $p\gg 1/n$ and to study the smoothed complexity of graph isomorphism. Our method allows obtaining precise results on the automorphism group of the core (Theorem 6).

Immerman and Lander [23] showed a tight connection between CR-identifiability and definability of a graph in first-order logic with counting quantifiers. Corollary 5 can, therefore, be recast in logical terms as follows. If $p=O(1/n)$ , then $\mathsf{H}_{n}$ is whp definable in this logic with using only two first-order variables (where the definability of a graph $H$ means the existence of a formula which is true on $H$ and false on any graph non-isomorphic to $H$ ). Definability of the giant component of $G(n,p)$ in the standard first-order logic (without counting quantifiers) was studied by Bohman et al. [11].

The rest of the paper and proof strategy.

Section 2 begins with formal description of the color refinement algorithm in Subsection 2.1 and then, in Subsection 2.2, presents a useful criterion of CR-distinguishability in terms of universal covers. The concept of a universal cover appeared in algebraic and topological graph theory [10, 15, 31], and its tight connection to CR was observed in [3]. Subsection 2.3 pays special attention to the CR-identifiability of unicyclic graphs, which in Subsection 2.4 allows us to obtain an explicit criterion of CR-identifiability for general graphs in terms of the complex and the simple part of a graph. Finally, in Subsection 2.5 we use the relationship between CR and universal covers to prove useful properties of the CR-coloring of the core of an arbitrary graph.

Theorem 1 and Corollaries 2 and 5 are proved in Section 3. The proofs of Theorem 1 and Corollary 5 are based on Theorem 3. A crucial ingredient of the proof of Theorem 3 is our Main Lemma (Lemma 20). This lemma says that CR is unable to distinguishe between two vertices in the core only if they lie either on pendant paths (with the same endvertices) transposable by an automorphism of the graph or on a pendant cycle admitting a reflection by an automorphism. Note that this statement alone, which is a part of the information provided by Theorem 3, is enough to derive Theorem 1 and Corollary 5.

The proof of Main Lemma is outlined in Section 4. It heavily relies on the notion of a kernel. The kernel $K(G)$ of a graph $G$ is a multigraph obtained from $\operatorname{core}(G)$ by contracting all pendant paths. That is, $K(G)$ is obtained via the following iterative procedure: at every step if there exists a vertex $u$ with only two neighbors $v_{1},v_{2}$ , we remove $u$ with both incident edges and add the edge $\{v_{1},v_{2}\}$ instead. Note that this transformation can lead to appearance of multiple edges and loops.

To prove that CR colors vertices of the core in the described manner, we use the contiguous models due to Ding, Lubetzky, and Peres [18] in strictly supercritical regime and due to Ding, Kim, Lubetzky, and Peres in critical regime [17]. They allow to transfer properties of random multigraphs with given degree sequences to the kernel of the giant component in the random graph. Another important ingredient in our proofs is the fact that in the kernel of the supercritical random graph there are whp no small complex subgraphs. We consider separately two types of vertices: first, we prove that CR colors differently all vertices such that their neighborhoods induce trees. This is done in Sections 4.1 and 4.2 for $p=1+\omega(n^{-1/3})$ and $p=1+O(n^{-1/3})$ respectively. Then, in Section 4.3, we prove that these vertices are helpful to distinguish between all the remaining vertices.

A complete proof of Theorem 3 and the proof of Theorem 6 are omitted due to the space constraints and can be found in the full version of the paper [33].

2 Color refinement: From identifiability to canonical labeling

2.1 Description of the CR algorithm

We now give a formal description of the color refinement algorithm (CR for short). CR operates on vertex-colored graphs but applies also to uncolored graphs by assuming that their vertices are colored uniformly. An input to the algorithm consists either of a single graph or a pair of graphs. Consider the former case first. For an input graph $G$ with initial coloring $C_{0}$ , CR iteratively computes new colorings

C_{i}(x)=\left(C_{i-1}(x),\left\{\!\!\left\{C_{i-1}(y)\right\}\!\!\right\}_{y% \in N(x)}\right),

(1)

where $\left\{\!\!\left\{\right\}\!\!\right\}$ denotes a multiset and $N(x)$ is the neighborhood of a vertex $x$ . Denote the partition of $V(G)$ into the color classes of $C_{i}$ by $\mathcal{P}_{i}$ . Note that each subsequent partition $\mathcal{P}_{i+1}$ is either finer than or equal to $\mathcal{P}_{i}$ . If $\mathcal{P}_{i+1}=\mathcal{P}_{i}$ , then $\mathcal{P}_{j}=\mathcal{P}_{i}$ for all $j\geq i$ . Suppose that the color partition stabilizes in the $t$ -th round, that is, $t$ is the minimum number such that $\mathcal{P}_{t}=\mathcal{P}_{t-1}$ . CR terminates at this point and outputs the coloring $C=C_{t}$ . Note that if the colors are computed exactly as defined by (1), they will require exponentially long color names. To prevent this, the algorithm renames the colors after each refinement step, using the same set of no more than $n$ color names.

If an input consists of two graphs $G$ and $H$ , then it is convenient to assume that their vertex sets $V(G)$ and $V(H)$ are disjoint. The vertex colorings of $G$ and $H$ define an initial coloring $C_{0}$ of the union $V(G)\cup V(H)$ , which is iteratively refined according to (1). The color partition $\mathcal{P}_{i}$ is defined exactly as above but now on the whole set $V(G)\cup V(H)$ . As soon as the color partition of $V(G)\cup V(H)$ stabilizes, CR terminates and outputs the current coloring $C=C_{t}$ of $V(G)\cup V(H)$ . The color names are renamed for both graphs synchronously.

We say that CR distinguishes $G$ and $H$ if $\left\{\!\!\left\{C(x)\right\}\!\!\right\}_{x\in V(G)}\neq\left\{\!\!\left\{C(% x)\right\}\!\!\right\}_{x\in V(H)}$ . If CR fails to distinguish $G$ and $H$ , then we call these graphs CR-equivalent and write $G\equiv_{\mathrm{CR}}H$ . A graph $G$ is called CR-identifiable if $G\equiv_{\mathrm{CR}}H$ always implies $G\cong H$ .

2.2 Covering maps and universal covers

A surjective homomorphism from a graph $K$ onto a graph $G$ is a covering map if its restriction to the neighborhood of each vertex in $K$ is bijective. We suppose that $G$ is a finite graph, while $K$ can be an infinite graph. If there is a covering map from $K$ to $G$ (in other terms, $K$ covers $G$ ), then $K$ is called a covering graph of $G$ . Let $G$ be connected. We say that a graph $U$ is a universal cover of a graph $G$ if $U$ covers every connected covering graph of $G$ . A universal cover $U=U^{G}$ of $G$ is unique up to isomorphism. Alternatively, $U^{G}$ can be defined as a tree that covers $G$ . If $G$ is itself a tree, then $U^{G}\cong G$ ; otherwise the tree $U^{G}$ is infinite.

A straightforward inductive argument shows that a covering map $\alpha$ preserves the coloring produced by CR, that is, $C_{i}(u)=C_{i}(\alpha(u))$ for all $i$ , where $C_{i}$ is defined by (1). It follows that, if two connected graphs $G$ and $H$ have a common universal cover, i.e., $U^{G}\cong U^{H}$ , then $\left\{\hskip 1.42262ptC(u):\hskip 1.42262ptu\in V(G)\right\}=\left\{\hskip 1.% 42262ptC(v):\hskip 1.42262ptv\in V(H)\right\}$ . The converse implication is also true, as a consequence of the following lemma.

Lemma 7 (cf. Lemmas 2.3 and 2.4 in [26]).

Let $U^{G}$ and $U^{H}$ be universal covers of connected graphs $G$ and $H$ respectively. Furthermore, let $\alpha$ be a covering map from $U^{G}$ to $G$ and $\beta$ be a covering map from $U^{H}$ to $H$ . For a vertex $x$ of $U^{G}$ and a vertex $y$ of $U^{H}$ , let $U^{G}_{x}$ and $U^{H}_{y}$ be the rooted versions of $U^{G}$ and $U^{H}$ with roots at $x$ and $y$ respectively. Then $U^{G}_{x}\cong U^{H}_{y}$ (isomorphism of rooted trees) if and only if $C(\alpha(x))=C(\beta(y))$ .

The union of CR-identifiable graphs does not need be CR-identifiable. However, the concept of a universal cover allows us to state the following criterion, which is an extension of [4, Thm. 5.4] (see [4, p. 649] for details).

Lemma 8.

Let $G_{1},\ldots,G_{k}$ be connected CR-identifiable graphs and $G$ be their vertex-disjoint union. Then $G$ is CR-identifiable if and only if, for every pair of distinct $i$ and $j$ such that neither $G_{i}$ nor $G_{j}$ is a tree, the universal covers of $G_{i}$ and $G_{j}$ are non-isomorphic.

2.3 Unicyclic graphs

2.3.1 Universal covers of unicyclic graphs

For a unicyclic graph $G$ , its $\operatorname{core}(G)$ is the set of vertices lying on the unique cycle of $G$ . We use the notation $c(G)=|\operatorname{core}(G)|$ for the length of this cycle. For a vertex $x$ in $\operatorname{core}(G)$ , let $G_{x}$ denote the subgraph of $G$ induced by the vertices reachable from $x$ along a path avoiding the other vertices in $\operatorname{core}(G)$ . This is obviously a tree. Moreover, we define $G_{x}$ as a rooted tree with root at $x$ . Let $t(x)$ denote the isomorphism class of the rooted tree $G_{x}$ . We treat $t$ as a coloring of $\operatorname{core}(G)$ and write $R(G)$ to denote the cycle of $G$ endowed with this coloring. Thus, $R(G)$ is defined as a vertex-colored cycle graph. It will also be useful to see $R(G)$ as a circular word over the alphabet $\{t(x)\,:\,\begin{array}[]{@{}l@{}}x\in\operatorname{core}(G)\end{array}\}$ ; see, e.g., [22] and the references therein for more details on this concept in combinatorics on words. In fact, $R(G)$ is associated with two circular words, depending on one of the two directions in which we go along $R(G)$ . However, the choice of one of the two words is immaterial in what follows.

Speaking about a word, we mean a standard, non-circular word. Two words are conjugated if they are obtainable from one another by cyclic shifts. A circular word is formally defined as the conjugacy class of a word. A word $u$ is a period of a word $v$ if $v=u^{k}$ for some $k\geq 1$ . A word $u$ is a period of a circular word $w$ if $u$ is a period of some representative in the conjugacy class of $w$ . Note that if $u$ is a period of a word $v$ , then any conjugate of $u$ is a period of some conjugate of $v$ . This allows us to consider periods of circular words themselves being circular words. We define the periodicity $p(w)$ of a circular word $w$ to be the minimum length of a period of $w$ . It may be useful to keep in mind that a period of length $p(w)$ is also a period of every period of $w$ ; cf. [22, Proposition 1] (note that our terminology is different from [22]).

For a unicyclic graph $G$ , we define its periodicity by $p(G)=p(R(G))$ , where $R(G)$ is seen as a circular word as explained above. Note that $p(G)$ is a divisor of $c(G)$ and that $1\leq|\left\{t(x)\right\}_{x\in\operatorname{core}(G)}|\leq p(G)\leq c(G)$ .

Like trees, unicyclic graphs are also characterizable in terms of universal covers.

$\vartriangleright$ Claim 9.

A connected graph $G$ is unicyclic if and only if $U^{G}$ has a unique infinite path.

The unique infinite path subgraph of $U^{G}$ will be denoted by $P(U_{G})$ . The structure of $U^{G}$ is clear: The cycle of $G$ is unfolded into the infinite path $P(U^{G})$ . Moreover, let $\alpha$ be a covering map from $U^{G}$ to $G$ . Then $U^{G}$ is obtained by planting a copy of the rooted tree $G_{\alpha(x)}$ at each vertex $x$ on $P(U^{G})$ . The path $P(U^{G})$ will be considered being a vertex colored graph, with each vertex $x$ colored by $t(\alpha(x))$ .

The following observation is quite useful in what follows. Let $\alpha$ be a covering map from $U^{G}$ to $G$ . The restriction of $\alpha$ to $P(U^{G})$ is a covering map from the vertex-colored path $P(U^{G})$ to the vertex-colored cycle $R(G)$ . Note that a covering map must preserve vertex colors.

Lemma 10.

Let $G$ and $H$ be connected unicyclic graphs. Then $U^{G}\cong U^{H}$ if and only if the circular words $R(G)$ and $R(H)$ have a common period. Moreover, if $U^{G}\cong U^{H}$ , then $p(G)=p(H)$ .

Proof.

In one direction the statement is clear: if $R(G)$ and $R(H)$ have a common period, then $U^{G}\cong U^{H}$ by the definition. Let $U\cong U^{G}\cong U^{H}$ be a common universal cover of $G$ and $H$ . We can naturally see $P(U)$ as an infinite word. An arbitrary subword of length $p(G)$ of $P(U)$ is a period of $P(U)$ , and the same is true for an arbitrary subword of length $p(H)$ of $P(U)$ . It follows that $P(U)$ has a period $u=u_{1}\ldots u_{q}$ of length $q=\gcd(p(G),p(H))$ . Indeed, it is sufficient to note that there exist integers $\beta_{1},\beta_{2}$ such that $q=\beta_{1}p(G)-\beta_{2}p(H)$ . Thus, for any $u_{0},u_{q}$ at distance $q$ in $P(U)$ , we get that $u_{0}=u_{\beta_{1}p(G)}=u_{q+\beta_{2}p(H)}=u_{q}$ .

If $\alpha$ and $\beta$ are covering maps from $U$ to $G$ and $H$ respectively, then $\alpha(u_{1})\ldots\alpha(u_{q})$ is a period of $R(G)$ and $\beta(u_{1})\ldots\beta(u_{q})$ is a period of $R(H)$ . Since $\alpha$ and $\beta$ preserve the vertex colors, we have the equality $\alpha(u_{1})\ldots\alpha(u_{q})=\beta(u_{1})\ldots\beta(u_{q})$ . This also implies that, in fact, $q=p(G)=p(H)$ . $\hfill\blacktriangleleft$

2.3.2 CR-identifiability of unicyclic graphs

$\vartriangleright$ Claim 11.

Let $G$ be a connected unicyclic graph. Suppose that $G\equiv_{\mathrm{CR}}H$ and $H$ consists of connected components $H_{1},\ldots,H_{m}$ . Then

1.

$U^{H_{i}}\cong U^{G}$ for all $i$ ,
2.

every $H_{i}$ is unicyclic, and
3.

$c(G)=c(H_{1})+\cdots+c(H_{m})$ .

Proof.

1. Fix $i\in[m]$ . Let $U^{G}$ and $W=U^{H_{i}}$ and $\alpha^{U},\alpha^{W}$ be the respective covering maps. Let $y$ be a vertex in $U^{H_{i}}$ . Since $G$ and $H$ are CR-equivalent, $U^{G}$ must contain a vertex $x$ such that $C(\alpha^{U}(x))=C(\alpha^{W}(y))$ . By Lemma 7, $U_{x}\cong W_{y}$ . It follows that $U\cong W$ .

2. Immediately by Part 1 and Claim 9.

3. Fix a period of $R(G)$ and set $T=\sum_{x}|V(G_{x})|$ where the summation goes over all $x$ in this period (this definition obviously does not depend on the choice of the period). Let $p=p(G)$ . Note that $|V(G)|=\frac{c(G)}{p}\,T$ . By Part 1 and Lemma 10, we similarly have $|V(H_{i})|=\frac{c(H_{i})}{p}\,T$ . The required equality now follows from the trivial equality $|V(G)|=|V(H_{1})|+\cdots+|V(H_{m})|$ . $\hfill\vartriangleleft$

Lemma 12.

A connected unicyclic graph $G$ is CR-identifiable if and only if one of the following conditions is true:

$\blacksquare$

$p(G)=1$ and $c(G)\in\{3,4,5\}$ ,
$\blacksquare$

$p(G)=2$ and $c(G)\in\{4,6\}$ ,
$\blacksquare$

$p(G)=c(G)$ .

Proof.

( $\Leftarrow$ ) Suppose that a connected unicyclic graph $G$ satisfies one of the three conditions and show that it is CR-identifiable. Assuming that $H$ is CR-equivalent to $G$ , we have to check that $G$ and $H$ are actually isomorphic.

Assume first that $H$ is connected. If $H$ is not unicyclic, then $G$ and $H$ have equal number of vertices but different number of edges. This implies that $G$ and $H$ have different degree sequences, contradicting the assumptions that $G\equiv_{\mathrm{CR}}H$ . Therefore, $H$ must be unicyclic. By Part 3 of Claim 11, we have $c(G)=c(H)$ . Along with Lemma 10, which is applicable because $U^{G}\cong U^{H}$ whenever $G\equiv_{\mathrm{CR}}H$ , this implies that $R(G)\cong R(H)$ . The last relation, in its turn, implies that $G\cong H$ .

Assume now that $H$ is disconnected. Let $H_{1},\ldots,H_{m}$ be the connected components of $H$ . Combining Claim 11 and Lemma 10, we see that $p(G)=p(H_{1})\leq c(H_{1})<c(G)$ . It follows that $G$ satisfies one of the first two conditions. The restrictions on $c(G)$ , however, rule out the equality in Part 3 of Claim 11. In particular, if $c(G)=6$ , then the only possible case is $m=2$ and $c(H_{1})=c(H_{2})=3$ . However, it contradicts the equality $p(H_{1})=p(H_{2})=p(G)=2$ . Thus, the case of disconnected $H$ is actually impossible, that is, all such $H$ are distinguishable from $G$ by CR.
( $\Rightarrow$ ) Suppose that all three conditions are false. That is, either $p(G)=1$ and $c(G)\geq 6$ , or $p(G)=2$ and $c(G)\geq 8$ (note that $c(G)$ is even in this case), or $3\leq p(G)<c(G)$ (in the last case, $p(G)$ is a proper divisor of $c(G)$ ). In each case, $R(G)$ is CR-equivalent to a disjoint union of two shorter vertex-colored cycles $R_{1}$ and $R_{2}$ , both sharing the same period of length $p(G)$ with $R(G)$ . Taking the connected unicyclic graphs $H_{1}$ and $H_{2}$ such that $R(H_{1})\cong R_{1}$ and $R(H_{2})\cong R_{2}$ , we see that $G$ is CR-equivalent to the disjoint union of $H_{1}$ and $H_{2}$ and is, therefore, not CR-identifiable. $\hfill\blacktriangleleft$

Lemma 13.

Let $G$ and $H$ be connected unicyclic graphs with $c(H)\leq c(G)$ . Assume that both $G$ and $H$ are CR-identifiable. Then $U^{G}\cong U^{H}$ if and only if $\{t(x)\,:\,\begin{array}[]{@{}l@{}}x\in\operatorname{core}(G)\end{array}\}=\{t% (x)\,:\,\begin{array}[]{@{}l@{}}x\in\operatorname{core}(H)\end{array}\}$ and one of the following conditions is true:

$\blacksquare$

$G\cong H$ ,
$\blacksquare$

$p(G)=p(H)=1$ and $3\leq c(H)<c(G)\leq 5$ ,
$\blacksquare$

$p(G)=p(H)=2$ and $c(H)=4$ while $c(G)=6$ .

Proof.

( $\Leftarrow$ ) By Lemma 10.
( $\Rightarrow$ ) Let $G$ and $H$ be CR-identifiable connected unicyclic graphs with $c(H)\leq c(G)$ . Assume that $U^{G}\cong U^{H}$ . The equality $\{t(x)\,:\,\begin{array}[]{@{}l@{}}x\in\operatorname{core}(G)\end{array}\}=\{t% (x)\,:\,\begin{array}[]{@{}l@{}}x\in\operatorname{core}(H)\end{array}\}$ immediately follows from Lemma 10. By the same corollary, $p(G)=p(H)=p$ . If $p\geq 3$ , then Lemma 12 yields the equality $c(G)=p(G)=p(H)=c(H)$ , which readily implies $G\cong H$ by using Lemma 10 once again. If $p\leq 2$ , then either $c(G)=c(H)$ and $G\cong H$ or $c(H)<c(G)$ and then, by Lemma 12, $c(H)$ and $c(G)$ are as claimed. $\hfill\blacktriangleleft$

2.4 A general criterion of CR-identifiability

Deciding whether a given graph is CR-identifiable is an efficiently solvable problem [4, 25]. For our purposes, it is beneficial to have a more explicit description of CR-identifiable graphs in terms of the complex and the simple part of a graph. We now derive such a description from the facts obtained for unicyclic graphs in the preceding subsection.

Theorem 14.

1.

A graph $G$ is CR-identifiable if and only if both the complex and the simple parts of $G$ are CR-identifiable.
2.
The simple part of $G$ is CR-identifiable if and only if both of the following two conditions are true:
1. (a)
  
  every unicyclic component of $G$ is CR-identifiable, i.e., is as described in Lemma 12;
2. (b)
  
  every two unicyclic components of $G$ have non-isomorphic universal covers, i.e., there is no pair of connected components as described in Lemma 13.

Proof.

1.

If $G$ is CR-identifiable, then its complex and simple parts are both CR-identifiable as a consequence a more general fact: The vertex-disjoint union of any set of connected components of $G$ is CR-identifiable. This fact is easy to see directly, and it also immediately follows from Lemma 8.

In the other direction, assuming that the complex and the simple parts of $G$ are CR-identifiable, we have to conclude that $G$ is CR-identifiable. Lemma 8 reduces our task to verification that if $H$ is a complex connected component of $G$ and $S$ is a simple connected component of $G$ (a tree or a unicyclic graph), then the universal covers of $H$ and $S$ are non-isomorphic. The last condition follows from the fact that the universal cover of a tree is the tree itself and from Claim 9.
2.

The second part of the theorem follows immediately from Lemma 8 due to the well-known fact [23] that every tree is CR-identifiable.

$\hfill\blacktriangleleft$

2.5 Coloring the cores of general graphs

We conclude this section by collecting useful general facts about the CR-colors of vertices in the core of a graph. Let $G$ be an arbitrary graph. If $x$ is a vertex in $\operatorname{core}(G)$ , then in $G$ we have a tree growing from the root $x$ that shares with $\operatorname{core}(G)$ only the vertex $x$ . We denote this rooted tree by $T_{x}$ .

$\vartriangleright$ Claim 15.

Let $G$ and $H$ be graphs. Let $x$ be a vertex in $\operatorname{core}(G)$ and $y$ be a vertex in $\operatorname{core}(H)$ . If $T_{x}\not\cong T_{y}$ , then $C(x)\neq C(y)$ .

Proof.

Clearly, it suffices to prove this for connected $G$ and $H$ . The condition $T_{x}\not\cong T_{y}$ readily implies that $U^{G}_{x}\not\cong U^{H}_{y}$ , and the claim follows from Lemma 7. $\hfill\vartriangleleft$

$\vartriangleright$ Claim 16.

Let $G$ and $H$ be two graphs (it is not excluded that $G=H$ ). For vertices $u\in V(G)$ and $v\in V(H)$ assume that $C(u)=C(v)$ . Then $u\in\operatorname{core}(G)$ if and only if $v\in\operatorname{core}(H)$ .

Proof.

Assume that $G$ and $H$ are connected (the general case will easily follow). Let $\alpha_{G}$ be a covering map from $U^{G}$ to $G$ , and $\alpha_{H}$ be a covering map from $U^{H}$ to $H$ . Consider $x\in V(U^{G})$ and $y\in V(U^{H})$ such that $\alpha_{G}(x)=u$ and $\alpha_{H}(y)=v$ . Note that $u\in\operatorname{core}(G)$ if and only if there is a cycle in $U^{G}$ containing $x$ , and the same is true about $v$ any $y$ . This proves the claim because $U^{G}_{x}\cong U^{H}_{y}$ by Lemma 7. $\hfill\vartriangleleft$

In our proofs, we will deal with cores that locally have a tree structure, that is, the balls of sufficiently large radii around most of its vertices induce trees. In this case, CR distinguishes vertices that have non-isomorphic neighborhoods.

$\vartriangleright$ Claim 17.

Let $B_{r}(v)$ denote the set of vertices at distance at most $r$ from a vertex $v$ . Let $v_{1},v_{2}\in V(G)$ . If, for some $r$ , the $r$ -neighborhoods $B_{r}(v_{1})$ and $B_{r}(v_{1})$ induce non-isomorphic trees rooted in $v_{1}$ and $v_{2}$ respectively, then $C(v_{1})\neq C(v_{2})$ .

Proof.

This is a direct consequence of Lemma 7. $\hfill\vartriangleleft$

Throughout the paper, we identify the vertex set of the kernel of $G$ with the set of vertices of $\operatorname{core}(G)$ having degrees at least 3 in the core. We now state another consequence of Lemma 7.

$\vartriangleright$ Claim 18.

Let $G$ be a graph with minimum degree at least 2 and let $\mathrm{K}$ be its kernel. Let $r$ be a positive integer. For $v\in V(\mathrm{K})$ , let $\mathcal{B}^{\mathrm{K}}_{r}(v)$ be the subgraph of $\mathrm{K}$ induced by the set of vertices at distance at most $r$ from $v$ in $\mathrm{K}$ . Let $\mathcal{B}_{r}(v)\subset G$ be the subdivided version of $\mathcal{B}^{\mathrm{K}}_{r}(v)$ . Let $v_{1},v_{2}$ be vertices of $\mathrm{K}$ such that, for some $r$ , graphs $\mathcal{B}_{r}(v_{1}),\mathcal{B}_{r}(v_{2})\subset G$ are non-isomorphic trees rooted in $v_{1},v_{2}$ . Then $C^{G}(v_{1})\neq C^{G}(v_{2})$ .

Finally, we need the fact that the partition produced by CR on a graph refines the partition produced by CR on its core.

$\vartriangleright$ Claim 19.

Let $u$ and $v$ be vertices in $\operatorname{core}(G)$ . Let $C$ and $C^{\prime}$ be the colorings produced by CR run on $G$ and $\operatorname{core}(G)$ respectively. If $C^{\prime}(u)\neq C^{\prime}(v)$ , then also $C(u)\neq C(v)$ .

Proof.

Clearly, it is enough to prove the claim for a connected graph $G$ . Let us assume towards a contradiction that $C(u)=C(v)$ . Let $\alpha$ be a covering map from $U^{G}$ to $G$ . Let $x,y\in V(U^{G})$ be such that $\alpha(x)=u$ and $\alpha(y)=v$ . Due to Lemma 7, $U^{G}_{x}\cong U^{G}_{y}$ . Therefore, $U^{\operatorname{core}(G)}_{x}=\operatorname{core}(U^{G}_{x})\cong% \operatorname{core}(U^{H}_{y})=U^{\operatorname{core}(H)}_{y}$ . But then, again by Lemma 7, $C^{\prime}(u)=C^{\prime}(v)$ , a contradiction. $\hfill\vartriangleleft$

3 Proofs of main results

3.1 Derivation of Corollary 5 from Theorem 3

Part 1.

Any isomorphism of graphs obviously respects their cores; cf. Claim 16. Note that the CR-color of any vertex $x$ in the core $\mathsf{C}_{n}$ contains a complete information about the isomorphism type of the rooted tree $T_{x}$ “growing” from this vertex (cf. Claim 15). This has the following consequence. Let $\mathsf{C}^{\prime}_{n}$ denote the colored version of $\mathsf{C}_{n}$ where each vertex $x$ is colored by the isomorphism type of $T_{x}$ . Then $\mathsf{H}_{n}$ is CR-identifiable if and only if $\mathsf{C}^{\prime}_{n}$ is CR-identifiable. In order to show that $\mathsf{C}^{\prime}_{n}$ is CR-identifiable it suffices to show that $\mathsf{C}^{\prime}_{n}$ is reconstructible up to isomorphism from the multiset of the vertex colors produced by CR on input $\mathsf{C}^{\prime}_{n}$ . The CR-color partition of $\mathsf{C}^{\prime}_{n}$ is equal to the restriction of the CR-color partition of $\mathsf{H}_{n}$ to $\mathsf{C}_{n}$ (recall Claim 16). Theorem 3, therefore, provides us with the following information (whp):³³3Note that Conditions (b) and (c) are provided by Main Lemma. Condition (a) is not essential for the argument in Subsections 3.1 and 3.2, which easily extends to the case of more than two mutually transposable pendant paths.

(a)

every CR-color class of $\mathsf{C}^{\prime}_{n}$ has size either 1 or 2,
(b)

every two equally colored vertices have degree 2,
(c)

every two equally colored vertices are transposable by an automorphism of $\mathsf{C}^{\prime}_{n}$ .

Moreover, our Main Lemma (Lemma 20) ensures that $\mathsf{H}_{n}$ whp has no involutory automorphism of type $A_{3}$ described in Section 1. Along with this fact, the above conditions readily imply that the color classes of size 2 occur either “along” a pair of transposable pendant paths between two vertices of degree at least 3 or correspond to the reflectional symmetry of a pendant cycle. Here we use the notions introduced in Section 1 in the context of $\operatorname{Aut}(\mathsf{C}_{n})$ , which should now be refined by taking into account the coloring of $\mathsf{C}^{\prime}_{n}$ .

If $\{u\}$ and $\{v\}$ are two color classes of size 1, then the colors $C(u)$ and $C(v)$ yield the information on whether the vertices $u$ and $v$ are adjacent or not. For color classes $\{u\}$ and $\{v,v^{\prime}\}$ , note that $u$ and $v$ are adjacent if and only if $u$ and $v^{\prime}$ are adjacent. This adjacency pattern is as well reconstructible from the colors $C(u)$ and $C(v)=C(v^{\prime})$ . If $\{u,u^{\prime}\}$ and $\{v,v^{\prime}\}$ are two color classes of size 2, then they span either a complete or empty bipartite graph or a matching (for example, $u$ is adjacent to $v$ , $u^{\prime}$ is adjacent to $v^{\prime}$ , and there is no other edges between these color classes). Each of these three possible adjacency patterns is reconstructible from the colors $C(u)=C(u^{\prime})$ and $C(v)=C(v^{\prime})$ . A crucial observation, completing the proof, is that all ways to put a matching between $\{u,u^{\prime}\}$ and $\{v,v^{\prime}\}$ lead to isomorphic graphs.

Part 2.

This follows from part 1 by part 1 of Theorem 14.

3.2 Derivation of Theorem 1 from Theorem 3

Before proceeding to the proof, we remark that when we say that a canonical labeling algorithm succeeds on a random graph $G_{n}$ , we mean that the algorithm works correctly on a certain efficiently recognizable (closed under isomorphisms) class of graphs $\mathcal{C}$ such that $G_{n}$ belongs to $\mathcal{C}$ whp. Though not explicitly stated in the argument below, it will be clear that, in our case, $\mathcal{C}$ is the class of all graphs satisfying the conditions of Theorem 3. Note that these conditions are easy to check after running CR on a graph.

First of all, we distinguish the complex and the simple parts of $G_{n}$ and compute a canonical labeling of the simple part separately. This is doable in linear time. It remains to handle the complex part $\mathsf{H}_{n}$ .

It is enough to compute a suitable injective coloring of $\mathsf{H}_{n}$ and subsequently to rename the colors in their lexicographic order by using the labels that were not used for the simple part. To this end, we run CR on $\mathsf{H}_{n}$ . This takes time $O(n\log n)$ as CR can be implemented [9] in time $O((n+m)\log n)$ , where $m$ denotes the number of edges (which is linear for the sparse random graph under consideration). Then we begin with coloring the vertices of the core $\mathsf{C}_{n}$ . Theorem 3 along with Claim 16 ensures that the vertices of degree at least 3 already received individual colors. The duplex colors occur along transposable pendant paths and pendant cycle (like in Section 3.1, these notions are understood with respect to $\mathsf{H}_{n}$ rather than to $\mathsf{C}_{n}$ alone). To make such vertex colors unique, we keep the original colors along one of two transposable paths and concatenate their counterparts in the other path with a special symbol. We proceed similarly with symmetric pendant cycles. In this way, every vertex $x$ in the core $\mathsf{C}_{n}$ receives an individual color $\ell(x)$ . In the last phase, we compute a canonical labeling for each tree part $T_{x}$ of $\mathsf{H}_{n}$ , regarding $T_{x}$ as a tree rooted at $x$ . This coloring is not injective yet because some $T_{x}$ and $T_{y}$ can be isomorphic. This is rectified by concatenating all vertex colors in $T_{x}$ with $\ell(x)$ .

3.3 Proof of Corollary 2

As well known, if $1/n\ll p\leq 1/2$ then the core of the giant component of $G(n,p)$ coincides with the core of the entire graph. Due to the classical linear-time algorithms for canonical labeling of trees, this observation reduces canonical labeling of $G(n,p)$ with $1/n\ll p\leq 1/2$ to canonical labeling of its core.

Linial and Mosheiff [27] suggested an algorithm ${\sf A}_{1}$ that, for any $p$ with $\frac{1}{n}\ll p(n)<n^{-2/3}$ , whp labels canonically $G(n,p)$ in time $O(n^{4})$ by distinguishing between all vertices of the core. In [16], it was proved that, if $\frac{\ln^{4}n}{n}\leq p\leq\frac{1}{2}$ , then CR whp distinguishes between all vertices of the entire $G(n,p)$ . Finally, our Theorem 1 provides an algorithm ${\sf A}_{2}$ that, for any $p=O(1/n)$ , whp labels canonically $G(n,p)$ in time $O(n\ln n)$ . Now, consider the following algorithm ${\sf A}$ :

1.

Run CR. If it colors differently all vertices, then halt and output the canonical labeling produced by CR.
2.

If the algorithm does not halt in Step 1, then run ${\sf A}_{1}$ . If it succeeds (i.e., colors differently all vertices in the core of the input graph), then halt and output the labeling produced by ${\sf A}_{1}$ .
3.

If the algorithm does not halt in Steps 1 and 2, then run ${\sf A}_{2}$ and output the labeling it produces (or give up if ${\sf A}_{2}$ fails).

Let us show that the algorithm ${\sf A}$ succeeds whp for any $p$ with $p(n)\leq 1/2$ . Assume, to the contrary, that there exist a constant $\varepsilon>0$ and a sequence $(n_{k})_{k\in\mathbb{N}}$ such that

\mathbb{P}({\sf A}\text{ fails on $G(n_{k},p(n_{k}))$})>\varepsilon

for all $k$ . If there is a subsequence $(n_{k_{i}})_{i\in\mathbb{N}}$ and a constant $C>0$ such that $p(n_{k_{i}})<C/n_{k_{i}}$ for all $i$ , then we get a contradiction with the performance of the algorithm ${\sf A}_{2}$ . Therefore, $p(n_{k})\gg\frac{1}{n_{k}}$ . If there is a subsequence $(n_{k_{i}})_{i\in\mathbb{N}}$ such that $p(n_{k_{i}})<n^{-2/3}_{k_{i}}$ for all $i$ , then we get a contradiction with the performance of the algorithm ${\sf A}_{1}$ . It follows that $p(n_{k})\geq n^{-2/3}_{k}$ for all $k$ . This, however, contradicts the result of [16] that CR in this regime produces a discrete coloring of $G(n,p)$ whp.

In order to obtain canonical labeling, whp, for all $p$ with $p(n)\in[0,1]$ , we run the algorithm ${\sf A}$ on input $G$ and if it fails, then we run ${\sf A}$ once again on the complement of $G$ .

4 CR-coloring of the random graph

In this section, we state and prove our Main Lemma that describes the output of CR on the random graph. Given a graph $G$ , we call vertices $u$ and $v$ in $\mathrm{core}(G)$ interchangeable, if

$\blacksquare$

they both have degree 2 in $\mathrm{core}(G)$ ,
$\blacksquare$

$u$ and $v$ belong to a cycle $F\subset\mathrm{core}(G)$ with the following property: there exists a vertex $w$ on the cycle such that $w$ has degree at least 3 in $\mathrm{core}(G)$ , $d_{F}(u,w)=d_{F}(v,w)$ , and all the other vertices on the cycle, but the vertex opposite to $w$ when $|V(F)|$ is even, have degree 2 in $\mathrm{core}(G)$ . In other words, $u$ and $v$ either belong to a pendant cycle or to two transposable pendant paths, and the respective transposition replaces $u$ and $v$ .

Lemma 20 (Main Lemma).

Let $\gamma>1$ be a constant, $pn\leq\gamma$ , and $G_{n}=G(n,p)$ . Let $\mathrm{H}_{n}$ be the union of complex components in $G_{n}$ , and $\mathrm{C}_{n}$ be its core. If CR is run on $\mathrm{H}_{n}$ , then whp any pair of vertices in $\mathrm{C}_{n}$ receiving the same color is interchangeable. Under the condition $pn=1+\omega(n^{-1/3})$ , this is true also if CR is run on $\mathrm{C}_{n}$ .

The proof of Main Lemma is given in Sections 4.1–4.3. We consider separately large $p$ (supercritical phase) and small $p$ (critical phase). In both cases, we specify good sets of vertices and show that all vertices from good sets are distinguished by CR. This is done in Section 4.1 for large $p$ and Section 4.2 for small $p$ . Finally, in Section 4.3 we complete the proof: we show that distinguishing between good vertices in the core is sufficient to distinguish between all pairs in the core that are not interchangeable.

For a graph $G$ , $d_{G}(u,v)$ is the shortest-path distance between $u$ and $v$ in $G$ . Sometimes, when the graph is clear from the context, we omit the subscript $G$ . For a vertex $v$ and a real number $r$ , we denote by $\mathcal{B}^{G}_{r}(v)$ the ball of radius $r$ around $v$ in $G$ , i.e., the graph induced on the set of all vertices at distance at most $r$ from $v$ in $G$ . For a non-negative integer $r$ , we denote by $\mathcal{S}^{G}_{r}(v)\subset\mathcal{B}^{G}_{r}(v)$ the sphere of radius $r$ around $v$ in $G$ , i.e., the graph induced on the set of all vertices at distance exactly $r$ from $v$ in $G$ .

For a connected graph $G$ , its excess is the difference between the number of edges and the number of vertices. In particular, a tree has excess $-1$ . We call $\ell$ -complex a connected graph with excess $\ell$ . The total excess of a graph without unicyclic components is the sum of excesses of all its components.

4.1 Distinguishing good vertices in the core in the supercritical and strictly supercritical phases

In this subsection, we let $p=p(n)$ be such that $\gamma\geq np=1+\omega(n^{-1/3})$ for some constant $\gamma>1$ . Denote $\delta_{n}:=np-1$ . We denote the kernel and the core of the giant component of $G_{n}\sim G(n,p)$ by $\mathrm{K}_{n}$ and $\mathrm{C}_{n}$ . Let $C^{\mathrm{core}}$ be the coloring produced by CR on $\mathrm{C}_{n}$ .

We assign to every edge $e$ of $\mathrm{C}_{n}$ the weight $1/\ell$ , where $\ell-1$ is the number of vertices that subdivide the edge of the kernel $e$ belongs to. The weight of a path is the sum of weights of its edges. For $u,v\in V(\mathrm{C}_{n})$ , let $d^{f}(u,v)$ be the fractional distance between $u$ and $v$ , i.e. the minimum weight of a path between $u$ and $v$ . We denote the respective metric space by $\mathcal{M}_{n}$ .

Fix a positive real $s$ . Let $D_{s}$ be the set of all $v\in V(\mathrm{C}_{n})$ such that the ball around $v$ in $\mathcal{M}_{n}$ of radius $s$ induces an acyclic graph. For every vertex $v\in D_{s}$ and integer $r<s$ , let $\mathcal{P}_{r}(v)$ be the multiset of lengths of edge-disjoint paths from $\mathrm{C}_{n}$ that are produced by subdividing edges $\{x,y\}\in E(\mathrm{K}_{n})$ , where $d^{f}(x,v)\leq r$ while $d^{f}(y,v)>r$ . We will need the following facts.

$\vartriangleright$ Claim 21.

Let $s\geq 0.6(\ln(\delta^{3}_{n}n))^{2/3}$ . Whp for any two different $u,v\in D_{s}\cap V(\mathrm{K}_{n})$ , there exists an integer $r\leq 0.5(\ln(\delta^{3}_{n}n))^{2/3}$ such that the multisets $\mathcal{P}_{r}(u)$ and $\mathcal{P}_{r}(v)$ are different.

Proof.

We fix $s\geq 0.6(\ln(\delta^{3}_{n}n))^{2/3}$ and let $D:=D_{s}$ . We prove this claim in the contiguous models $\tilde{G}_{n}$ , defined in [17, Thm. 2] and [18, Thm. 1] and then use these theorems to conclude that it also holds in $G_{n}$ . So, in what follows, $\mathrm{\tilde{K}}_{n}=\mathrm{K}(\tilde{G}_{n})$ , $\mathrm{\tilde{C}}_{n}=\mathrm{C}(\tilde{G}_{n})$ , and $\tilde{D}=D(\tilde{K}_{n})$ .

Let us expose $\mathrm{\tilde{K}}_{n}$ and let $u,v\in\tilde{D}\cap V(\mathrm{\tilde{K}}_{n})$ . As proved in [17, 18], whp $N=|V(\tilde{K}_{n})|=\Theta(\delta^{3}_{n}n)$ . Assume first that the distance between $u$ and $v$ is at most $0.4(\ln(\delta^{3}_{n}n))^{2/3}$ in $\mathrm{\tilde{K}}_{n}$ . Let $P$ be the shortest path between $u$ and $v$ – it is unique due to the definition of $\tilde{D}$ . Let $v^{\prime}$ be a neighbor of $v$ in $\mathrm{\tilde{K}}_{n}$ that does not belong to $P$ . Then, by the definition of $\tilde{D}$ , $\left|\mathcal{S}^{\mathrm{\tilde{K}}_{n}}_{r}(v^{\prime})\setminus\mathcal{B}% ^{\mathrm{\tilde{K}}_{n}}_{r}(v)\right|\geq 2^{r}$ for all $r\in\left[0.4(\ln(\delta^{3}_{n}n))^{2/3},0.5(\ln(\delta^{3}_{n}n))^{2/3}\right]$ . Since $u,v\in\tilde{D}$ , we have that $\mathcal{B}^{\mathrm{\tilde{K}}_{n}}_{s}(u)$ and $\mathcal{B}^{\mathrm{\tilde{K}}_{n}}_{s}(v)$ are trees. It immediately implies, that for every such $r$ , $\left|\mathcal{S}^{\mathrm{\tilde{K}}_{n}}_{r+1}(v)\setminus\mathcal{B}^{% \mathrm{\tilde{K}}_{n}}_{r+1}(u)\right|\geq 2^{r}.$

We then generate subdivisions of the edges of the kernel from the definition of $\tilde{G}_{n}$ in the following order: for every $r=\left\lceil 0.4(\ln(\delta^{3}_{n}n))^{2/3}\right\rceil,\ldots,\left\lfloor 0% .5(\ln(\delta^{3}_{n}n))^{2/3}\right\rfloor$ , we, first, subdivide all edges growing from $\mathcal{B}^{\mathrm{\tilde{K}}_{n}}_{r+1}(u)$ outside of the ball, and then all edges growing from $\mathcal{S}^{\mathrm{\tilde{K}}_{n}}_{r+1}(v)$ outside of $\mathcal{B}^{\mathrm{\tilde{K}}_{n}}_{r+1}(v)$ . Notice that all sets $\mathcal{S}^{\mathrm{\tilde{K}}_{n}}_{r+1}(v)$ are disjoint for different $r$ . For every $r$ , as soon as the edges that correspond to the vertex $u$ are subdivided, the event that $\mathcal{P}_{r+1}(u)=\mathcal{P}_{r+1}(v)$ immediately implies that the random multiset of lengths of paths from $\mathrm{\tilde{C}}_{n}$ , that are produced by subdividing edges from $\mathrm{\tilde{K}}_{n}$ that grow from $\mathcal{B}_{r+1}^{\mathrm{\tilde{K}}_{n}}(v)$ outside, should be equal to a predefined value. This multiset has size at least $2^{r}$ . Since the geometric random variables considered in [17, 18] do not have atoms with probability measure $1-o(1)$ , the latter event has probability at most $2^{-\Theta(r)}$ due to the de Moivre–Laplace local limit theorem. Eventually,

\mathbb{P}\left(\mathcal{P}_{r+1}(u)=\mathcal{P}_{r+1}(v)\text{ for all }r\in\left[0.4(\ln(\delta^{3}_{n}n))^{2/3},0.5(\ln(\delta^{3}_{n}n))^{2/3}% \right]\right)\leq\\ \leq\exp\left(-\Theta((\log(\delta^{3}_{n}n))^{4/3})\right).

Assume now that the distance between $u$ and $v$ is bigger than $0.4(\ln(\delta^{3}_{n}n))^{2/3}$ in $\mathrm{\tilde{K}}_{n}$ . Then, by the definition of $\tilde{D}$ , sets $\mathcal{B}^{\mathrm{\tilde{K}}_{n}}_{0.2(\ln(\delta^{3}_{n}n))^{2/3}}(v)$ and $\mathcal{B}^{\mathrm{\tilde{K}}_{n}}_{0.2(\ln(\delta^{3}_{n}n))^{2/3}}$ are disjoint and sets $\mathcal{S}^{\mathrm{\tilde{K}}_{n}}_{r}(v)$ have size at least $2^{r}$ for all $r\in[0.15(\ln(\delta^{3}_{n}n))^{2/3},0.2(\ln(\delta^{3}_{n}n))^{2/3}-1]$ . As above, we get that $\mathcal{P}_{r}(u)=\mathcal{P}_{r}(v)$ for all $r\in\left[0.15(\ln(\delta^{3}_{n}n))^{2/3},0.2(\ln(\delta^{3}_{n}n))^{2/3}-1\right]$ with probability at most $\exp\left(-\Theta((\log(\delta^{3}_{n}n))^{4/3})\right)$ .

The union bound over all pairs $u,v\in\tilde{D}$ along with [17, Thm. 2] and [18, Thm. 1] completes the proof. $\hfill\vartriangleleft$

$\vartriangleright$ Claim 22.

Let $s^{*}:=\lfloor(\ln(\delta^{3}_{n}n))^{2/3}\rfloor$ and $D=D_{s^{*}}$ . Whp, $C^{\mathrm{core}}(u)\neq C^{\mathrm{core}}(v)$ for any distinct $u,v\in D$ .

Proof.

Assume that the assertion of Claim 21 holds for $s=s^{*}$ and $s=s^{*}-1$ deterministically. Let $u,v\in D\cap V(\mathrm{K}_{n})$ . Let $B_{u}$ and $B_{v}$ be the subdivided versions of $\mathcal{B}_{s^{*}}^{\mathrm{K}_{n}}(u)$ and $\mathcal{B}_{s^{*}}^{\mathrm{K}_{n}}(v)$ in $\mathrm{C}_{n}$ . Since $B_{u}\ncong B_{v}$ due to the conclusion of Claim 21, we get that $C^{\mathrm{core}}(u)\neq C^{\mathrm{core}}(v)$ due to Claim 18. It remains to consider the case $v\in D\setminus V(\mathrm{K}_{n})$ and $v\neq u\in D$ . Assume towards contradiction that $C^{\mathrm{core}}(u)=C^{\mathrm{core}}(v)$ . Then, both $u$ and $v$ have degree 2 in $\mathrm{C}_{n}$ . In particular, $u\notin V(\mathrm{K}_{n})$ . Consider the edges $e_{u},e_{v}$ of $\mathrm{K}_{n}$ that $u$ and $v$ subdivide. Let $P_{u},P_{v}$ be the subdivided versions of $e_{u},e_{v}$ . Due to the assertion of Claim 21 applied to $s=s^{*}-1$ , we get that all vertices of $\mathrm{K}_{n}$ from $e_{u}\cup e_{v}$ have different colors. On the other hand, by the definition of CR, the neighbors of $u$ should have exactly the same color as the neighbors of $v$ . Thus, by induction, we get that the entire paths $P_{u},P_{v}$ are colored identically. It may only happen if the endpoints of $P_{u}$ coincide with the endpoints of $P_{v}$ . By the definition of $D$ , it means that $P_{u}=P_{v}=:P$ . Since the endpoints of $P$ are colored in different colors, it can be easily shown by induction that all vertices in $P$ are also colored in different colors. Thus, $u=v$ , yielding a contradiction. $\hfill\vartriangleleft$

4.2 Distinguishing good vertices in the core in the critical regime

Let $A$ be a large positive number. Let $1-n^{-1/3}\ln n\leq pn=1+o(1)$ . Whp any complex component in $G_{n}\sim G(n,p)$ has size at least $100A\ln n$ due to the following well-known fact.

$\vartriangleright$ Claim 23.

Let $\gamma>1$ , $np\leq\gamma$ , and $G_{n}\sim G(n,p)$ . There exists $\varepsilon=\varepsilon(\gamma)$ such that $\varepsilon\to\infty$ as $\gamma\to 1$ and whp any connected subgraph of $G_{n}$ of size at most $\varepsilon\ln n$ is not complex.

Let us say that a path $u_{1}\ldots u_{k}$ extends the path $v_{1}\ldots v_{k}$ if, for some $i\in\{2,\ldots,k\}$ the sets $\{v_{1},\ldots,v_{i-1}\}$ and $\{u_{k-i+2},\ldots,u_{k}\}$ are disjoint and $u_{1}=v_{i},\ldots,u_{k-i+1}=v_{k}$ . For convenience, we assume that this notion is closed under rotations of paths, i.e. if $u_{1}\ldots u_{k}$ extends $v_{1}\ldots v_{k}$ , then it also extends $v_{k}\ldots v_{1}$ and we also say that $u_{k}\ldots u_{1}$ extends both $v_{1}\ldots v_{k}$ and $v_{k}\ldots v_{1}$ in this case. We call two paths $v_{1}\ldots v_{k}$ and $u_{1}\ldots u_{k}$ weakly disjoint, if they are either vertex-disjoint or one paths extends the other one.

$\vartriangleright$ Claim 24.

Whp in $G_{n}$ there are no two weakly disjoint paths $v_{1}\ldots v_{k}$ and $u_{1}\ldots u_{k}$ of length $k=\lfloor A\ln n\rfloor$ such that, for every $i\in\{2,\ldots,k-1\}$ , $v_{i}$ has degree 2 if and only if $u_{i}$ has degree 2.

Proof.

Due to Claim 23, whp in $G_{n}$ there are no complex subgraphs with at most $2k$ vertices.

For a path $P=v_{1}\ldots v_{k}$ in $G_{n}$ , let us consider a binary word $w(P)=(w_{2},\ldots,w_{k-1})$ defined as follows: $w_{i}=1$ if and only if $v_{i}$ has degree $2$ in $G_{n}$ . Notice that, if a path $u_{1}\ldots u_{k}$ extends the path $v_{1}\ldots v_{k}$ so that $u_{1}=v_{i},\ldots,u_{k-i+1}=v_{k}$ and $w(v_{1}\ldots v_{k})=w(u_{1}\ldots u_{k})$ , then $w(u_{1}\ldots u_{k})$ is periodic and defined by $w(v_{1}\ldots v_{i+1})=(w_{2},\ldots,w_{i})$ .

Let $X$ be the number of pairs of paths as in the statement of the claim and such that there are at most 2 edges between the paths (we are allowed to assume this since there are no complex subgraphs of size at most $2k$ ). Fix two weakly disjoint path $\mathbf{v}=v_{1}\ldots v_{k}$ and $\mathbf{u}=u_{1}\ldots u_{k}$ and assume without loss of generality that either $\mathbf{u}$ extends $\mathbf{v}$ , or they are disjoint. Let $i$ be such that $u_{1}=v_{i}$ . If there is no such $i$ , i.e. the paths are disjoint, set $i=k+1$ . Then, expose edges from all $v_{j}$ , $j\leq i$ , and assume that they send at most 2 edges to $u_{2},\ldots,u_{k-1}$ , other than the edge $\{u_{1},u_{2}\}$ . Then, probability that for every $j\in\{2,\ldots,k-1\}$ , $v_{j}$ has degree 2 if and only if $u_{j}$ has degree 2, is at most

\max\left\{(1-p)^{n-2k},(1-(1-p)^{n})\right\}^{k-4}\leq\left(1-e^{-(1+o(1))}% \right)^{k-4}=o\left(\left(\frac{2}{3}\right)^{k}\right).

We then get

\mathbb{E}X\leq\sum_{i=2}^{k+1}n^{k+i-1}p^{k+i-3}\left(\frac{2}{3}\right)^{k}% \leq kn^{2}(1+o(1))^{2k}\left(\frac{2}{3}\right)^{k}=o(1),

for an appropriate choice of $A$ . Due to Markov’s inequality, $\mathbb{P}(X\geq 1)\leq\mathbb{E}X=o(1)$ , completing the proof. $\hfill\vartriangleleft$

Let $D$ be the set of all vertices $v$ in $\mathrm{C}_{n}=\mathrm{core}(G_{n})$ that belong to a complex component of $G_{n}$ and such that $B_{v}:=\mathcal{B}^{G_{n}}_{3A\ln n}(v)$ is a tree. Let $C$ be the coloring produced by CR on $G_{n}$ .

$\vartriangleright$ Claim 25.

Whp, $C(u)\neq C(v)$ for any $u,v\in D$ .

Proof.

Assume that the statement of Claim 24 holds deterministically in $G_{n}$ . Fix two different $u,v\in D$ . Let us show towards contradiction that trees $B_{v}$ and $B_{u}$ are not isomorphic.

Take an arbitrary path $v_{1}\ldots v_{k}$ of length $k:=\lfloor 1.9A\ln n\rfloor$ , where $v_{1}=v$ . Since, by assumption, $B_{v}\cong B_{u}$ , there exists a path $\mathbf{u}=u_{1}\ldots u_{k}$ such that $u_{1}=u$ and, for every $i\in\{2,\ldots,k-1\}$ , $v_{i}$ has degree 2 if and only if $u_{i}$ has degree 2. In the same way, since $v\in\mathrm{core}(G_{n})$ and $B_{v}$ is a tree, we may consider a path $v^{\prime}_{1}\ldots v^{\prime}_{k}$ that shares only the vertex $v^{\prime}_{1}=v=v_{1}$ with $v_{1}\ldots v_{k}$ . Since $B_{u}\cong B_{v}$ , there should be a path $\mathbf{u}^{\prime}=u^{\prime}_{1}\ldots u^{\prime}_{k}$ that shares with $u_{1}\ldots u_{k}$ the only vertex $u^{\prime}_{1}=u=u_{1}$ and such that, for every $i\in\{2,\ldots,k-1\}$ , $v^{\prime}_{i}$ has degree 2 if and only if $u^{\prime}_{i}$ has degree 2. Since $B_{v}$ is acyclic and since pairs of paths $v_{1}\ldots v_{k},\,u_{1}\ldots u_{k}$ and $v^{\prime}_{1}\ldots v^{\prime}_{k},\,u^{\prime}_{1}\ldots u^{\prime}_{k}$ cannot be disjoint due to Claim 24, $u$ must lie on the path $P:=v_{k}\ldots v_{1}\ldots v_{k}^{\prime}$ . Moreover, since $B_{u}$ is acyclic, once $\mathbf{u}$ or $\mathbf{u}^{\prime}$ leave $P$ , they never meet with $P$ again. Thus, the path $u_{k}\ldots u_{1}\ldots u_{k}^{\prime}$ is divided by $P$ in at most 3 parts: the first part does not have common vertices with $P$ , the second part is a subpath of $P$ , and the third part does not have common vertices with $P$ again. Let $Q$ be the longest part of the three. Then $Q$ has length $\ell\geq\frac{1}{3}(2k-1)>A\ln n$ . Moreover, since $\mathrm{deg}_{G_{n}}u=\mathrm{deg}_{G_{n}}v$ by assumption and $u\neq v$ , there should be a subpath $P^{\prime}\subset P$ such that $P^{\prime}$ and $Q$ are weakly disjoint, and the degrees of internal vertices in $P^{\prime}$ and $Q$ are aligned in the sense that the $i$ -th inner vertex of $P^{\prime}$ have degree 2 if and only if the $i$ -th vertex of $Q$ has degree 2. This is impossible due to Claim 24. Thus, $B_{v}\ncong B_{u}$ implying $C(u)\neq C(v)$ due to Claim 17. $\hfill\vartriangleleft$

4.3 Completing the proof of Main Lemma (Lemma 20)

Due to Claims 22, 25, and 19, it remains to prove the following:

1.
If $1+\omega(n^{-1/3})=pn\leq\gamma$ , then
- $\blacksquare$
  
  $C^{\mathrm{core}}(u)\neq C^{\mathrm{core}}(v)$ for every $v\in V(\mathrm{C}_{n})\setminus D$ and $u\in D$ ;
- $\blacksquare$
  
  $C^{\mathrm{core}}(u)\neq C^{\mathrm{core}}(v)$ for any non-interchangeable pair $u,v\in V(\mathrm{C}_{n})\setminus D$ ;
2.
If $1-n^{-1/3}\ln n\leq pn=1+o(1)$ , then
- $\blacksquare$
  
  $C(u)\neq C(v)$ for every $v\in V(\mathrm{C}_{n})\setminus D$ and $u\in D$ ;
- $\blacksquare$
  
  $C(u)\neq C(v)$ for any non-interchangeable pair $u,v\in V(\mathrm{C}_{n})\setminus D$ .

We will use the following technical fact, which follows from [17, Thm. 2] and [18, Thm. 1].

$\vartriangleright$ Claim 26.

Let $\delta>0$ be a constant, $n^{-1/3}\ll\delta_{n}:=pn-1\leq\delta$ , and $G_{n}\sim G(n,p)$ . Then whp in $K(G_{n})$ there are no complex subgraphs of size at most $(\ln(n\delta^{3}_{n}))^{3/4}$ .

For the sake of brevity, below we prove both statements in two different regimes simultaneously. Thus, with some abuse of notation, in the supercritical phase (i.e., $1+\omega(n^{-1/3})=pn\leq\gamma$ ), we let $G_{n}:=\mathrm{C}_{n}$ and $C:=C^{\mathrm{core}}$ as we only consider CR on $\mathrm{C}_{n}$ . We also assume that when $1+\omega(n^{-1/3})=pn\leq\gamma$ , the core is equipped with the fractional distance $d^{f}$ , constituting the metric space $\mathcal{M}_{n}$ . If $1-n^{-1/3}\ln n\leq pn\leq 1+o(1)$ , then $G_{n}$ is equipped with the usual shortest-path distance, that we denote by $d^{f}$ as well. We also use the following notation: $d=\lfloor(\ln(\delta_{n}^{3}n))^{2/3}\rfloor$ when we prove the assertion for $1+\omega(n^{-1/3})=pn\leq\gamma$ and $d=\lfloor 3A\ln n\rfloor$ when we prove it for $1-n^{-1/3}\ln n\leq pn=1+o(1)$ . In what follows, we assume that the assertions of Claims 22, 23, 25, and 26 hold deterministically in $G_{n}$ .

1.

Assume that some $v\notin D$ and $u\in D$ have $C(u)=C(v)$ . We know that $v$ is $d$ -close to a cycle $F$ of length at most $2d$ . If $v\in V(F)$ , then let $v^{\prime}$ be the closest to $v$ vertex on $F$ that has degree more than 2 in the core. Otherwise, let $v^{\prime}=v$ . Let $P$ be the shortest path from $v^{\prime}$ to $F$ . Let us extend this path by a path $P^{\prime}$ of length $10d$ beyond $v^{\prime}$ . Due to Claim 23 and Claim 26, it has a subpath $w\ldots w^{\prime}$ of length $5d$ consisting of vertices from $D$ only such that $d^{f}(w,v^{\prime})\leq d$ . We know that all elements of the vector $\mathbf{c}:=(C(w),\ldots,C(w^{\prime}))$ are different. Then, due to our assumption, $u$ must have a vertex $z$ at distance at most $d^{f}(w,v)$ such that $z$ is the first vertex of a path $z\ldots z^{\prime}$ with $C(w)=C(z)$ , $\ldots,$ $C(w^{\prime})=C(z^{\prime})$ .

We now consider separately two cases: $w=z$ and $w\neq z$ . In the first case, we have that the distance from $u$ to the closest cycle (which is $F$ , the same as for $v$ ) is at most

$d^{f}(w,u)+d^{f}(w,v^{\prime})+d^{f}(v^{\prime},F)\leq\text{length of }F+2(d^{% f}(w,v^{\prime})+d^{f}(v^{\prime},F))\leq 6d.$

Let $P$ be the shortest path between $u$ and $v$ . Due to Claim 23 and Claim 26, there exists a path $u\tilde{w}\ldots\tilde{w}^{\prime}$ of length $5d+1$ that does not meet $P$ and consists of vertices from $D$ only. Due to Claim 22 and Claim 25 all elements of the vector $\mathbf{\tilde{c}}:=(C(\tilde{w}),\ldots,C(\tilde{w}^{\prime}))$ are different and no element of $\mathbf{\tilde{c}}$ equals to any element of $\mathbf{c}$ . Moreover, by construction, $d^{f}(v,\tilde{w})>d^{f}(u,\tilde{w})$ . Then, due to our assumption, $v$ must have a neighbor $\tilde{z}\neq\tilde{w}$ such that $\tilde{z}$ is the first vertex of a path $\tilde{z}\ldots\tilde{z}^{\prime}$ with $C(\tilde{w})=C(\tilde{z})$ , $\ldots,$ $C(\tilde{w}^{\prime})=C(\tilde{z}^{\prime})$ . Note that $\tilde{w}\neq\tilde{z},\ldots,\tilde{w}^{\prime}\neq\tilde{z}^{\prime}$ due to Claim 23 and Claim 26. Since all vertices in $D$ are distinguished by $C(\cdot)$ , we conclude that all vertices $\tilde{z},\ldots,\tilde{z}^{\prime}$ must be outside $D$ . Due to Claim 23, Claim 26, and the definition of $D$ , they constitute a (self-avoiding) path and are $d$ -close to a cycle of length at most $2d$ . Since the path has length $5d$ , we get a contradiction with Claim 23 or Claim 26.

We then assume $w\neq z$ . It may only happen when $z\notin D$ . Moreover, all $z,\ldots,z^{\prime}$ are not in $D$ . Indeed, otherwise, different paths $w\ldots w^{\prime}$ and $z\ldots z^{\prime}$ have common vertices. Then the path from $z$ to $F$ that goes through $w$ has length greater than $d$ . However, due to Claim 23 and Claim 26, there are no two different paths from $z$ to $F$ , both of length at most $12d$ and, also, there is no other cycle $F^{\prime}$ of length at most $2d$ such that a path from $z$ to $F^{\prime}$ has at most $d$ vertices. This contradicts the fact that $z\notin D$ . Thus, we again get a (self-avoiding) path consisting of vertices $z,\ldots,z^{\prime}$ that are $d$ -close to a cycle of length at most $2d$ . This contradicts Claim 23 or Claim 26 again, since the path has length $5d$ . We conclude that every vertex $u\in D$ has $C(u)$ that does not equal to the color of any other vertex in the core.
2.

It remains to prove that, for any two distinct $u,v\notin D$ that are not interchangeable, $C(u)\neq C(v)$ . Fix two such vertices $u$ and $v$ . We may assume that $T_{u}\cong T_{v}$ since otherwise $C(u)\neq C(v)$ due to Claim 15. Let $F_{u}$ and $F_{v}$ be two cycles of length at most $2d$ that are closest to $u$ and $v$ respectively (both are at distance at most $d$ from the respective vertices). If $F_{u}\neq F_{v}$ , then set $F:=F_{u}$ . In this case, we let $u^{\prime}=u$ when $u\notin V(F)$ and let $u^{\prime}$ be the closest vertex of degree 3 in $F$ to $u$ otherwise. If $F_{u}=F_{v}=:F$ , then, without loss of generality we assume that either $u$ is not in $F$ or both $u, v$ are in $F$ . Let $u^{\prime}=u$ when $u\notin V(F)$ and let $u^{\prime}$ be a vertex of $F$ that has degree at least 3 and such that $d^{f}(u,u^{\prime})\neq d^{f}(v,u^{\prime})$ otherwise. Note that such a vertex exists due to the definition of an interchangeable pair. Consider a path $P$ of length $10d$ that starts at $u^{\prime}$ and does not meet $F$ . Due to Claim 23 and Claim 26, this path has a vertex $w$ in $D$ such that $d(w,u^{\prime})\leq d$ . If $F_{u}\neq F_{v}$ , then

$d^{f}(v,w)\geq d^{f}(F_{u},F_{v})-d^{f}(v,F_{v})-d^{f}(w,F_{u})>d^{f}(u,w)$

due to Claim 23 and Claim 26. Finally, let $F_{u}=F_{v}$ . Assume, in addition, $u\notin V(F)$ . Then the only possibility for $C(u)$ to be equal to $C(v)$ is to have a path $P^{\prime}$ between $v$ and $w$ of length $d^{f}(u,w)$ . Let us extend $P^{\prime}$ by a path of length $10d$ beyond $v$ . Due to Claim 23 and Claim 26 this path has a vertex $w^{\prime}$ from $D$ such that $d^{f}(w^{\prime},v)\leq d$ . But then $d^{f}(u,w^{\prime})>d^{f}(v,w^{\prime})$ , implying $C(u)\neq C(v)$ . If $u,v\in V(F)$ , then

$d^{f}(v,w)=d^{f}(v,u^{\prime})+d^{f}(u^{\prime},w)\neq d^{f}(u,u^{\prime})+d^{% f}(u^{\prime},w)=d^{f}(u,w).$

In either case, we get $d^{f}(v,w)\neq d^{f}(u,w)$ or $C(u)\neq C(v)$ . Recalling that $w$ has a unique color, we readily conclude that $C(u)\neq C(v)$ , completing the proof.

References

[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullmann. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., 1974.
[2] Michael Anastos, Matthew Kwan, and Benjamin Moore. Smoothed analysis for graph isomorphism, 2024. arXiv:2410.06095.
[3] D. Angluin. Local and global properties in networks of processors. In The 12th Annual ACM Symposium on Theory of Computing, pages 82–93, 1980.
[4] Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism, color refinement, and compactness. Comput. Complex., 26(3):627–685, 2017. doi:10.1007/s00037-016-0147-6.
[5] L. Babai, P. Erdős, and S. M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9(3):628–635, 1980. doi:10.1137/0209047.
[6] László Babai. Moderately exponential bound for Graph Isomorphism. In Proc. of the 3rd Int. Conf. on Fundamentals of Computation Theory (FCT’81), volume 117 of Lecture Notes in Computer Science, pages 34–50. Springer, 1981. doi:10.1007/3-540-10854-8_4.
[7] László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC’16), pages 684–697, 2016. doi:10.1145/2897518.2897542.
[8] László Babai. Canonical form for graphs in quasipolynomial time: preliminary report. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC’19), pages 1237–1246, 2019. doi:10.1145/3313276.3316356.
[9] Cristoph Berkholz, Paul Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60:581–614, 2017. doi:10.1007/S00224-016-9686-0.
[10] N. Biggs. Algebraic graph theory. Cambridge University Press, 2nd edition, 1994.
[11] Tom Bohman, Alan M. Frieze, Tomasz Luczak, Oleg Pikhurko, Clifford D. Smyth, Joel Spencer, and Oleg Verbitsky. First-order definability of trees and sparse random graphs. Comb. Probab. Comput., 16(3):375–400, 2007. doi:10.1017/S0963548306008376.
[12] Bela Bollobás. Distinguishing vertices of random graphs. Ann. Discrete Math., 13:33–50, 1982.
[13] Bela Bollobás. The evolution of random graphs. Transactions of the American Mathematical Society, 286(1):257–274, 1984.
[14] Bela Bollobás. Random graphs. Cambridge University Press, 2001.
[15] D. M. Cvetković, M. Doob, and H. Sachs. Spectra of graphs. Theory and applications. Leipzig: J. A. Barth Verlag, 3rd edition, 1995.
[16] Tomek Czajka and Gopal Pandurangan. Improved random graph isomorphism. Journal of Discrete Algorithms, 6:85–92, 2008. doi:10.1016/J.JDA.2007.01.002.
[17] Jian Ding, Jeong Han Kim, Eyal Lubetzky, and Yuval Peres. Anatomy of young giant component in the random graph. Random Structures & Algorithms, 39(2):139–178, 2011. doi:10.1002/RSA.20342.
[18] Jian Ding, Eyal Lubetzky, and Yuval Peres. Anatomy of the giant component: The strictly supercritical regime. European Journal of Combinatorics, 35:155–168, 2014. doi:10.1016/J.EJC.2013.06.004.
[19] Paul Erdős and Alfred Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17–61, 1960.
[20] Paul Erdős and Alfred Rényi. Asymmetric graphs. Acta Math Acad Sci Hung, 14:295–315, 1963.
[21] Julia Gaudio, Miklós Z. Rácz, and Anirudh Sridhar. Average-case and smoothed analysis of graph isomorphism, 2023. arXiv:2211.16454.
[22] László Hegedüs and Benedek Nagy. On periodic properties of circular words. Discrete Mathematics, 339(3):1189–1197, 2016. doi:10.1016/j.disc.2015.10.043.
[23] Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81. Springer New York, 1990.
[24] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random graphs. John Wiley & Sons, 2000.
[25] Sandra Kiefer, Pascal Schweitzer, and Erkal Selman. Graphs identified by logics with counting. ACM Trans. Comput. Log., 23(1):1:1–1:31, 2022. doi:10.1145/3417515.
[26] Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’15), pages 689–700. IEEE Computer Society, 2015. doi:10.1109/LICS.2015.69.
[27] N. Linial and J. Mosheiff. On the rigidity of sparse random graphs. Journal of Graph Theory, 85(2):466–480, 2017. doi:10.1002/JGT.22073.
[28] T. Łuczak. The automorphism group of random graphs with a given number of edges. Math Proc Camb Phil Soc, 104:441–449, 1988.
[29] Tomasz Łuczak. The phase transition in a random graph. In D. Miklós, V.T. Sós, and T. Szőnyi, editors, Combinatorics, Paul Erdős is Eighty, volume 2, pages 399–422. Bolyai Soc. Math. Stud. 2, J. Bolyai Math. Soc., Budapest, 1996.
[30] Tomasz Łuczak, Boris Pittel, and John C. Wierman. The structure of a random graph at the point of the phase transition. Transactions of the American Mathematical Society, 341(2):721–748, 1994.
[31] W. S. Massey. Algebraic topology: An introduction, volume 56 of Graduate Texts in Mathematics. Springer, 5th edition, 1981.
[32] Marc Noy, Vlady Ravelomanana, and Juanjo Rué. On the probability of planarity of a random graph near the critical point. Proc. Am. Math. Soc., 143(3):925–936, 2015. doi:10.1090/S0002-9939-2014-12141-1.
[33] Oleg Verbitsky and Maksim Zhukovskii. Canonical labeling of sparse random graphs, 2024. arXiv:2409.18109.
[34] B.Yu. Weisfeiler and A.A. Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Ser. 2, 9:12–16, 1968. In Russian. English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.
[35] E. M. Wright. Asymmetric and symmetric graphs. Glasgow Math J, 15:69–73, 1974.

[bib.bib1] [1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullmann. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., 1974.

[bib.bib2] [2] Michael Anastos, Matthew Kwan, and Benjamin Moore. Smoothed analysis for graph isomorphism, 2024. arXiv:2410.06095.

[bib.bib3] [3] D. Angluin. Local and global properties in networks of processors. In The 12th Annual ACM Symposium on Theory of Computing, pages 82–93, 1980.

[bib.bib4] [4] Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism, color refinement, and compactness. Comput. Complex., 26(3):627–685, 2017. doi:10.1007/s00037-016-0147-6.

[bib.bib5] [5] L. Babai, P. Erdős, and S. M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9(3):628–635, 1980. doi:10.1137/0209047.

[bib.bib6] [6] László Babai. Moderately exponential bound for Graph Isomorphism. In Proc. of the 3rd Int. Conf. on Fundamentals of Computation Theory (FCT’81), volume 117 of Lecture Notes in Computer Science, pages 34–50. Springer, 1981. doi:10.1007/3-540-10854-8_4.

[bib.bib7] [7] László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC’16), pages 684–697, 2016. doi:10.1145/2897518.2897542.

[bib.bib8] [8] László Babai. Canonical form for graphs in quasipolynomial time: preliminary report. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC’19), pages 1237–1246, 2019. doi:10.1145/3313276.3316356.

[bib.bib9] [9] Cristoph Berkholz, Paul Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60:581–614, 2017. doi:10.1007/S00224-016-9686-0.

[bib.bib10] [10] N. Biggs. Algebraic graph theory. Cambridge University Press, 2nd edition, 1994.

[bib.bib11] [11] Tom Bohman, Alan M. Frieze, Tomasz Luczak, Oleg Pikhurko, Clifford D. Smyth, Joel Spencer, and Oleg Verbitsky. First-order definability of trees and sparse random graphs. Comb. Probab. Comput., 16(3):375–400, 2007. doi:10.1017/S0963548306008376.

[bib.bib12] [12] Bela Bollobás. Distinguishing vertices of random graphs. Ann. Discrete Math., 13:33–50, 1982.

[bib.bib13] [13] Bela Bollobás. The evolution of random graphs. Transactions of the American Mathematical Society, 286(1):257–274, 1984.

[bib.bib14] [14] Bela Bollobás. Random graphs. Cambridge University Press, 2001.

[bib.bib15] [15] D. M. Cvetković, M. Doob, and H. Sachs. Spectra of graphs. Theory and applications. Leipzig: J. A. Barth Verlag, 3rd edition, 1995.

[bib.bib16] [16] Tomek Czajka and Gopal Pandurangan. Improved random graph isomorphism. Journal of Discrete Algorithms, 6:85–92, 2008. doi:10.1016/J.JDA.2007.01.002.

[bib.bib17] [17] Jian Ding, Jeong Han Kim, Eyal Lubetzky, and Yuval Peres. Anatomy of young giant component in the random graph. Random Structures & Algorithms, 39(2):139–178, 2011. doi:10.1002/RSA.20342.

[bib.bib18] [18] Jian Ding, Eyal Lubetzky, and Yuval Peres. Anatomy of the giant component: The strictly supercritical regime. European Journal of Combinatorics, 35:155–168, 2014. doi:10.1016/J.EJC.2013.06.004.

[bib.bib19] [19] Paul Erdős and Alfred Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17–61, 1960.

[bib.bib20] [20] Paul Erdős and Alfred Rényi. Asymmetric graphs. Acta Math Acad Sci Hung, 14:295–315, 1963.

[bib.bib21] [21] Julia Gaudio, Miklós Z. Rácz, and Anirudh Sridhar. Average-case and smoothed analysis of graph isomorphism, 2023. arXiv:2211.16454.

[bib.bib22] [22] László Hegedüs and Benedek Nagy. On periodic properties of circular words. Discrete Mathematics, 339(3):1189–1197, 2016. doi:10.1016/j.disc.2015.10.043.

[bib.bib23] [23] Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81. Springer New York, 1990.

[bib.bib24] [24] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński. Random graphs. John Wiley & Sons, 2000.

[bib.bib25] [25] Sandra Kiefer, Pascal Schweitzer, and Erkal Selman. Graphs identified by logics with counting. ACM Trans. Comput. Log., 23(1):1:1–1:31, 2022. doi:10.1145/3417515.

[bib.bib26] [26] Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’15), pages 689–700. IEEE Computer Society, 2015. doi:10.1109/LICS.2015.69.

[bib.bib27] [27] N. Linial and J. Mosheiff. On the rigidity of sparse random graphs. Journal of Graph Theory, 85(2):466–480, 2017. doi:10.1002/JGT.22073.

[bib.bib28] [28] T. Łuczak. The automorphism group of random graphs with a given number of edges. Math Proc Camb Phil Soc, 104:441–449, 1988.

[bib.bib29] [29] Tomasz Łuczak. The phase transition in a random graph. In D. Miklós, V.T. Sós, and T. Szőnyi, editors, Combinatorics, Paul Erdős is Eighty, volume 2, pages 399–422. Bolyai Soc. Math. Stud. 2, J. Bolyai Math. Soc., Budapest, 1996.

[bib.bib30] [30] Tomasz Łuczak, Boris Pittel, and John C. Wierman. The structure of a random graph at the point of the phase transition. Transactions of the American Mathematical Society, 341(2):721–748, 1994.

[bib.bib31] [31] W. S. Massey. Algebraic topology: An introduction, volume 56 of Graduate Texts in Mathematics. Springer, 5th edition, 1981.

[bib.bib32] [32] Marc Noy, Vlady Ravelomanana, and Juanjo Rué. On the probability of planarity of a random graph near the critical point. Proc. Am. Math. Soc., 143(3):925–936, 2015. doi:10.1090/S0002-9939-2014-12141-1.

[bib.bib33] [33] Oleg Verbitsky and Maksim Zhukovskii. Canonical labeling of sparse random graphs, 2024. arXiv:2409.18109.

[bib.bib34] [34] B.Yu. Weisfeiler and A.A. Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Ser. 2, 9:12–16, 1968. In Russian. English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.

[bib.bib35] [35] E. M. Wright. Asymmetric and symmetric graphs. Glasgow Math J, 15:69–73, 1974.

Canonical Labeling of Sparse Random Graphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Corollary 2.

Theorem 3.

▶ Remark 4.

Corollary 5.

Theorem 6.

Related work.

The rest of the paper and proof strategy.

2 Color refinement: From identifiability to canonical labeling

2.1 Description of the CR algorithm

2.2 Covering maps and universal covers

Lemma 7 (cf. Lemmas 2.3 and 2.4 in [26]).

Lemma 8.

2.3 Unicyclic graphs

2.3.1 Universal covers of unicyclic graphs

⊳ Claim 9.

Lemma 10.

Proof.

2.3.2 CR-identifiability of unicyclic graphs

⊳ Claim 11.

Proof.

Lemma 12.

Proof.

Lemma 13.

Proof.

2.4 A general criterion of CR-identifiability

Theorem 14.

Proof.

2.5 Coloring the cores of general graphs

⊳ Claim 15.

Proof.

⊳ Claim 16.

Proof.

⊳ Claim 17.

Proof.

⊳ Claim 18.

⊳ Claim 19.

Proof.

3 Proofs of main results

3.1 Derivation of Corollary 5 from Theorem 3

Part 1.

Part 2.

3.2 Derivation of Theorem 1 from Theorem 3

3.3 Proof of Corollary 2

4 CR-coloring of the random graph

Lemma 20 (Main Lemma).

4.1 Distinguishing good vertices in the core in the supercritical and strictly supercritical phases

⊳ Claim 21.

Proof.

⊳ Claim 22.

Proof.

4.2 Distinguishing good vertices in the core in the critical regime

⊳ Claim 23.

⊳ Claim 24.

Proof.

⊳ Claim 25.

Proof.

4.3 Completing the proof of Main Lemma (Lemma 20)

⊳ Claim 26.

References

$\blacktriangleright$ Remark 4.

$\vartriangleright$ Claim 9.

$\vartriangleright$ Claim 11.

$\vartriangleright$ Claim 15.

$\vartriangleright$ Claim 16.

$\vartriangleright$ Claim 17.

$\vartriangleright$ Claim 18.

$\vartriangleright$ Claim 19.

$\vartriangleright$ Claim 21.

$\vartriangleright$ Claim 22.

$\vartriangleright$ Claim 23.

$\vartriangleright$ Claim 24.

$\vartriangleright$ Claim 25.

$\vartriangleright$ Claim 26.