Chromatic number of G_{m,t} is Θ(t²)
Informal Conjecture on Chromatic Number of $G_{m,t}$ · arXiv:2103.05998
Status open high confidence
Alon's paper establishes that the chromatic number of $G_{m,t}$ (for $4t^2 \leq m$) lies between $2t$ and $O(t^2)$, and the conjecture that it equals $\Theta(t^2)$ remains open. Several papers have cited the 2021 paper for its main hitting-set result, but none found address the specific chromatic number question. This side conjecture, though stated as one raised more than ten years ago, has no resolved follow-up in the indexed literature.
Reviewer notes. The conjecture concerns the chromatic number of the specific graph $G_{m,t}$ constructed in the proof of Theorem 1.4, as a side problem to the main hitting-set result. Papers citing arXiv:2103.05998 found in search (e.g., arXiv:2302.04986 on P5-free graphs, arXiv:2403.19737 on piercing independent sets) address the hitting-set aspect of the paper, not the chromatic number conjecture. No follow-up resolving the $\Theta(t^2)$ conjecture was found.
Context
Alon states this as a conjecture he raised more than ten years ago, motivated by results in [2] (Alon, Hassidim, Lubetzky, Stav and Weinstein, FOCS 2008) and mentioned in several lectures. The paper establishes that the chromatic number is at least $2t$ and at most $O(t^2)$, leaving the exact order unresolved.
Notes. Stated informally in the Remarks section (Section 3) without a labelled theorem environment; attributed to the author himself from more than ten years prior but cited only via lectures, not a prior publication.
Source paper
Hitting all maximum independent sets
Noga Alon · 2021-04-04
https://arxiv.org/abs/2103.05998
PDF source