Coloring powers of random graphs

Abstract

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 $\hat{I}”(G_{n,p}^r)$ and the chromatic number $\ddot{I}‡(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.~$\hat{I}”(G_{n,p}^r)\sim \frac{\log n}{{\log }_{(r+1)}n}$ (where ${\log }_{(1)}n=\log n$ and ${\log }_{(r+1)}n=\log {\log }_{(r)}n$) and that w.h.p.~$\hat{I}”(G_{n,p}^{\lfloor r/2\rfloor })+1\le \ddot{I}‡(G_{n,p}^r)\le \hat{I}”(G_{n,p}^{r-1})+1$. For $r=2$, we show the upper bound holds with equality. For denser cases, for $d$ satisfying $d=\ddot{I}‰(\log n)$ and $d\le n^{1/r-\hat{I}\text{c◯}(1)}$ as $n\to \infty$, we have $\ddot{I}‡(G_{n,p}^r)=\hat{I}˜(d^r/\log d)$ w.h.p.