Existence of the $q$-Colorability Threshold for Sparse Random Graphs

For a fixed integer $q \ge 3$, we call a graph $q$-colorable if its vertices admit $q$ colors with adjacent vertices colored differently. We prove that there exists $d_q > 0$ such that the random graph on $n$ vertices with independent edge probability $d/n$ is $q$-colorable with probability tending to one for fixed $0 \le d < d_q$ and to zero for fixed $d > d_q$, as $n \to \infty$. The same holds for the uniform random graph with $\lfloor cn \rfloor$ edges, for fixed $c \ge 0$, with threshold $d_q/2$ in $c$. For fixed $\epsilon \in (0, 1)$, the first loss of colorability under independent uniform additions of pairs of distinct vertices lies with probability at least $1 - \epsilon$ in a deterministic window of $O_{q, \epsilon}(n(\log n)^{-3/2})$ steps, where $\log$ is natural. The proof uses interpolation to establish convergence and bounds the expected number of pairs needed to destroy colorability of the last colorable graph by identifying random vertices and controlling the growth of classes equal in every coloring.