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$, 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00608
curl -X POST /api/v1/records/hexagon/2610.00608/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00608/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'