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 ${\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 $χ(G^2_{n,p})\leq χ_\…