χ = χ_ℓ = χ_DP threshold for ω = Δ−1
Question 5 · arXiv:2603.14427
Status open high confidence
Question 5 asks for the smallest threshold \Delta_0 such that every graph G with \Delta(G) \geq \Delta_0 and \omega(G) = \Delta(G)-1 satisfies \chi(G) = \chi_{\ell}(G) = \chi_{DP}(G). The source paper itself (Theorem 4) provides an upper bound \Delta_0 \leq 3 \cdot 10^9 for the correspondence coloring analogue, while noting the equality trivially holds for \omega = \Delta+1 and \omega = \Delta; the exact threshold remains unknown. No subsequent paper resolving or sharpening this specific equality threshold was found in searches conducted two months after posting.
Reviewer notes. No follow-up addressing the specific threshold \Delta_0 for equality \chi = \chi_{\ell} = \chi_{DP} when \omega(G) = \Delta(G)-1 was found. A companion paper arXiv:2603.16670 (also March 2026) improves the purely chromatic Borodin-Kostochka bound to \Delta \geq 5.3 \times 10^6 but does not address the equality question. The conjecture is less than two months old as of the review date, so 'open' with high confidence is appropriate.
Context
Theorem 4 of this paper gives an upper bound $\Delta_0 \leq 3\cdot 10^9$ for the correspondence coloring analogue. The equality $\chi(G)=\chi_\ell(G)=\chi_{DP}(G)$ clearly holds for all graphs $G$ with $\omega(G)=\Delta(G)+1$, and the parameters also coincide for graphs with $\omega(G)=\Delta(G)$; the smallest threshold $\Delta_0$ for the case $\omega(G)=\Delta(G)-1$ remains unknown.
Source paper
On Borodin-Kostochka conjecture for correspondence coloring
Zdeněk Dvořák, Ross J. Kang, David Mikšaník · 2026-03-15
https://arxiv.org/abs/2603.14427