A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
Abstract
Let ζ(G) denote the minimum number of parts in a partition of V(G) in which every part induces either a clique or an independent set. Erdős and Gimbel asked whether, for Gn∼ G(n,1/2), the difference χ(Gn)−ζ(Gn) tends to infinity with high probability. We resolve this problem along the full sequence n→∞ and prove that ℙ(χ(Gn)−ζ(Gn)≥ ((log 2)2/4)log(200/153) n/(log n)3)→1. This gives a lower bound at the conjectured scale n/(log n)3. We also obtain a phase-resolved refinement: if δn is the fractional part of the standard independence-number center, then the coefficient may be replaced by (log 2)2A4(δn)/4−o(1), where A4 is explicit, continuous, nonconstant, and satisfies A4(δ)>log(200/153) for every δ∈[0,1]. The proof uses signed cocoloring profiles supported on four consecutive class sizes and remains uniform across jumps of the natural class-size cutoff. An exact signed-overlap identity separates local cell rewards from a binary cycle-space factor. A canonical decomposition into high cells and a capped residual matching, together with an endpoint-table comparison and an injective restriction of residual even edge sets, yields the required second-moment bound. A bounded-differences argument then amplifies the resulting rare signed witness to a high-probability cocoloring.
Related
- Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Bounds on the maximum denominator of fractional chromatic numbers
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
- Albertson's Conjecture for Chromatic Numbers at Most 29
BibTeX
@misc{petkov2026fullsequence,
title = {{A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph}},
author = {Samuil Petkov},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30604},
eprint = {2608.30604},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30604},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
AU - Samuil Petkov
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30604
UR - https://arxiv.org/abs/2608.30604
AB - Let ζ(G) denote the minimum number of parts in a partition of V(G) in which every part induces either a clique or an independent set. Erdős and Gimbel asked whether, for G_n∼ G(n,1/2), the difference χ(G_n)−ζ(G_n) tends to infinity with high probability. We resolve this problem along the full sequence n→∞ and prove that ℙ(χ(G_n)−ζ(G_n)≥ ((log 2)^2/4)log(200/153) n/(log n)^3)→1. This gives a lower bound at the conjectured scale n/(log n)^3. We also obtain a phase-resolved refinement: if δ_n is the fractional part of the standard independence-number center, then the coefficient may be replaced by (log 2)^2A_4(δ_n)/4−o(1), where A_4 is explicit, continuous, nonconstant, and satisfies A_4(δ)>log(200/153) for every δ∈[0,1]. The proof uses signed cocoloring profiles supported on four consecutive class sizes and remains uniform across jumps of the natural class-size cutoff. An exact signed-overlap identity separates local cell rewards from a binary cycle-space factor. A canonical decomposition into high cells and a capped residual matching, together with an endpoint-table comparison and an injective restriction of residual even edge sets, yields the required second-moment bound. A bounded-differences argument then amplifies the resulting rare signed witness to a high-probability cocoloring.
ER -