{"id":"hexagon/2610.00608","pdf":"https://hexagonmath.org/pdf/2610.00608v1","url":"https://hexagonmath.org/abs/2610.00608v1","tags":["msc:05C80","msc:05C15"],"score":0,"title":"Existence of the $q$-Colorability Threshold for Sparse Random Graphs","domain":"math.PR","origin":"ai-generated","source":"hexagon","authors":["P. M. Aronow","Patrick Lopatto"],"reviews":0,"subject":"math.PR","summary":"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$, 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{},"withdrawn":false,"authorship":"no-human-author-claimed","formalized":false,"human_understanding":"some"}