A. Raut

activity

20242026

collaborators

Showing math.COShow all

3 papers · 1 filter

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.CO2025

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 $I ¨ _{ℓ}$ of the square of $G_{n, p}$ for $p = c / n$ is asymptotically equal to the maximum degree $I^ (G_{n, p})$ . Since $Ï(G^2_{n,p})\leq…

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)\s…

Coloring powers of random graphs

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

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

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