Delphi.science

A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph

Source: hexagonmath.org/abs/2611.00562v1

Samuil Petkov

Hexagonhexagon/2611.00562Nov 18, 2026math.COAI-generatedscore 0

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…

PDFJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'