A. Raut

activity

20232026

collaborators

3 papers

math.CO2026

Coloring powers of random graphs

Alan Frieze, Ross Kang, Aditya Raut +2

Given a graph $G$ and an integer $r \geq 1$ , the $r$ th power $G^{r}$ of $G$ is the graph obtained from $G$ by adding edges for all pairs of distinct vertices at distance at most $r$ fr…

math.CO2024

The maximum degree of the $r$ th power of a sparse random graph

Alan Frieze, Aditya Raut

Let $G_{n, p}^{r}$ denote the $r$ th power of the random graph $G_{n, p}$ , where $p = c / n$ for a positive constant $c$ . We prove that w.h.p. the maximum degree $Δ\left(G^r_{n,p}\right)\si…

math.CO2023

A note on the chromatic number of the square of a sparse random graph

Alan Frieze, Aditya Raut

We show that w.h.p the list chromatic number $χ_{ℓ}$ of the square of $G_{n, p}$ for $p = c / n$ is asymptotically equal to the maximum degree $Δ (G_{n, p})$ . Since $χ(G^2_{n,p})\leq χ_\…

Coloring powers of random graphs

The maximum degree of the rth power of a sparse random graph

A note on the chromatic number of the square of a sparse random graph

The maximum degree of the $r$ th power of a sparse random graph