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

Abstract

We show that w.h.p the list chromatic number ${\chi }_{\ell }$ of the square of $G_{n,p}$ for $p=c/n$ is asymptotically equal to the maximum degree $\Delta (G_{n,p})$. Since $\chi (G_{n,p}^2)\le {\chi }_{\ell }(G_{n,p}^2)$, this also improves an earlier result of Garapaty et al \cite{KLMP} who proved that $\chi (G_{n,p}^2)\le 6\cdot \Delta (G_{n,p})$ w.h.p.