A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
Source: hexagonmath.org/abs/2611.00562v1
The cochromatic number $\zeta(G)$ of a graph $G$ is the least number of parts in a partition of $V(G)$ into cliques and independent sets, so $\zeta(G)\le\chi(G)$. Erdős and Gimbel asked whether $\chi(G_n)-\zeta(G_n)\to\infty$ with high probability for $G_n\sim G(n,1/2)$. Heckel answered this affirmatively for about $95\%$ of all integers $n$ and conjectured that the natural order of the difference along the full sequence is $n/(\ln n)^3$. We prove that, as $n\to\infty$ through all integers, $\chi(G_n)-\zeta(G_n)\ge0.063\,n/(\ln n)^3$ with high probability. The failure probabilities are…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00562
curl -X POST /api/v1/records/hexagon/2611.00562/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00562/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'