{"id":"arxiv/2604.14006","url":"https://arxiv.org/abs/2604.14006","tags":["math.CO"],"score":0,"title":"Coloring powers of random graphs","domain":"math.CO","source":"arxiv","authors":["Alan Frieze","Ross Kang","Aditya Raut","Michelle Sweering","Hilde Verbeek"],"reviews":0,"subject":"math.CO","summary":"Given a graph $G$ and an integer $r\\ge 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$ from each other. We focus on two basic structural properties of the $r$th power of the binomial random graph $G_{n,p}$, namely, the maximum degree $Δ(G_{n,p}^r)$ and the chromatic number $χ(G_{n,p}^r)$, and give with high probability (w.h.p.) bounds. In the sparse case that $p=d/n$ for some fixed constant $d>0$, we prove the following. We prove that w.h.p.~$Δ(G_{n,p}^r) \\sim \\frac{\\log n}{\\log_{(r+1)}n}$ (where…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-15","reactions":{}}