Random Graph Correspondence Chromatic Number Θ(n/log n)
Conjecture 1.4 · arXiv:2307.15048
Status open high confidence
Conjecture 1.4 from Dvořák–Yepremyan (arXiv:2307.15048) asserts that for every fixed $p\in(0,1]$, the Erdős–Rényi random graph $G(n,1-p)$ a.a.s. has correspondence chromatic number $\Theta(n/\log n)$. The source paper itself establishes the upper bound $O(n/\sqrt{\log n})$, which is weaker than the conjectured bound; the lower bound $\Omega(n/\log n)$ follows from the independence number. No subsequent paper resolving or making partial progress on the full $\Theta(n/\log n)$ claim was found in a wide search of arXiv and journal literature through May 2026.
Reviewer notes. No follow-up resolving the conjecture was found. The related paper arXiv:2308.13742 (Bernshteyn, 'DP-Coloring of Graphs from Random Covers', published RSA 2025) treats DP-coloring thresholds for random k-fold covers of a fixed graph — a different model — and its abstract does not address Conjecture 1.4 from 2307.15048. The gap between the known upper bound $O(n/\sqrt{\log n})$ and the conjectured $O(n/\log n)$ remains open; the authors note that a disproof would yield a new separation between list and correspondence chromatic numbers.
Context
Theorem 1.1 gives the upper bound $O(n/\sqrt{\log n})$, and both extreme cases of the correspondence assignment—matching the list-coloring setting and a fully random assignment for $K_n$ (Theorem 1.3)—only require $O(n/\log n)$ colors. The authors suspect the upper bound can be improved to match the lower bound $\Omega(n/\log n)$ coming from the independence number. They also note that a disproof would yield a new example separating list and correspondence chromatic numbers.
Notes. PDF source; special characters (Erdős-Rényi) rendered via ASCII in extraction but mathematical content is unambiguous.
Source paper
Correspondence coloring of random graphs
Zdenek Dvorak, Liana Yepremyan · 2023-07-27
https://arxiv.org/abs/2307.15048
PDF source