Id: arxiv/2603.14427 Url: https://arxiv.org/abs/2603.14427 Tags: math.CO Score: 0 Title: On Borodin-Kostochka conjecture for correspondence coloring Domain: math.CO Source: arxiv Authors: Zdeněk Dvořák, Ross J. Kang, David Mikšaník Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-15 Page: https://delphi.science/r/arxiv/2603.14427 Borodin and Kostochka in 1977 conjectured that if a graph $G$ has maximum degree $Δ(G)\ge 9$ and its clique number satisfies $ω(G)\le Δ(G)-1$, then its chromatic number satisfies $χ(G) \le Δ(G)-1$. We prove this statement with respect to a stronger graph coloring parameter, the correspondence chromatic number $χ_{DP}$, provided the maximum degree is sufficiently large. More precisely, we prove that for every integer $Δ\ge 3\cdot 10^9$, a graph $G$ of maximum degree at most $Δ$ satisfies $χ_{DP}(G) \le \max(ω(G),Δ-1)$. This strengthens earlier results of Reed (1999) for usual chromatic number…