On the Borodin--Kostochka conjecture for graphs with large maximum degree

Abstract

The Borodin--Kostochka conjecture states that every graph $G$ with maximum degree $\Delta (G)\ge 9$ satisfies $\chi (G)\le \max \{\omega (G),\Delta (G)-1\}$. In this paper, we verify this conjecture for graphs with sufficiently large maximum degree. More precisely, we prove that every graph $G$ with maximum degree $\Delta \ge 5.3\times 10^6$ and clique number $\omega (G)<\Delta$ satisfies $\chi (G)\le \Delta -1$. This improves a longstanding result of Reed.