The Borodin-Kostochka conjecture asserts that a finite simple graph 
with maximum vertex degree 
satisfies
 |
where 
is the chromatic number and 
is the clique number
(Borodin and Kostochka 1977).
Reed (1999) proved the inequality for sufficiently large maximum vertex degree. Chen (2026) obtained the explicit threshold 
using a randomized partial vertex
coloring and finite certified estimates. The conjecture remains open at the threshold
9.
