Chromatic number conjecture for powers of random graphs

Let $G_{n,p}$ be the random graph on $n$ vertices, let $G_{n,p}^r$ denote its $r$th power, and write $\chi(G)$ and $\alpha(G)$ for the chromatic and independence numbers of a graph $G$, respectively. Writing $\omega(G)$ for its clique number, let $p=d/n$, where $d>0$ is a constant and let $r\geq 1$ be a fixed positive integer. Chromatic number conjecture. With high probability,

$$\chi(G_{n,p}^r)=\Theta\left(\max\left\{\omega(G_{n,p}^r),\frac{n}{\alpha(G_{n,p}^r)}\right\}\right).$$

The conjecture proposes that the chromatic number of a fixed power of a sparse random graph is determined, up to constant factors, by the larger of its clique-number lower bound and the lower bound obtained from its independence number. The preceding results identify distinct regimes in which chromatic number appears to be locally or globally determined; the conjectured equivalence remains open.