The Borodin–Kostochka inequality from degree 750

Abstract

We prove that every finite simple graph $G$ with maximum degree at least $750$ satisfies $χ(G)\le\max\{ω(G),Δ(G)-1\}$. The proof starts with a random partial colouring and completes it on large cliques using a list-colouring condition that remains valid as the rest of the graph is coloured. Disjoint stars provide the required colours. We estimate the number of stars that can be chosen after the clique colours have been exposed, while keeping their endpoint set fixed. A common exponential-moment argument reduces intervals of packing sizes to endpoint comparisons. More detailed neighbourhood estimates handle the remaining vertices. The final probability inequalities are verified by directed rational and interval arithmetic.