The Borodin-Kostochka conjecture, posed in 1977, states that for any graph where the maximum number of edges meeting at a single vertex (called the maximum degree) is at least 9, the number of colors needed to properly color the graph is at most the larger of two quantities: the size of the biggest complete subgraph (clique number) or the maximum degree minus one. Intuitively, this says that unless a graph contains a large clique forcing you to use many colors, you can almost always do better than the naive greedy bound of using one color per degree. This paper proves that the conjecture holds for all graphs where the maximum degree is at least 750, which is the best verified threshold to date.
The proof strategy combines probabilistic and combinatorial techniques. The authors start by randomly assigning colors to part of the graph, leaving some vertices uncolored. The tricky part is then handling dense regions, particularly large cliques, where vertices are all mutually connected and each needs a distinct color. They use a tool from list-coloring theory to manage these cliques carefully, ensuring the partial coloring can be extended. The key device for supplying the needed colors is collections of "disjoint stars," simple tree-like substructures in the graph, which help organize which colors are available where.
The technical core of the argument involves carefully estimating how many such star structures can be found and used without interfering with each other, even after some color choices have already been committed to cliques. The authors reduce complicated probability estimates to comparisons between specific numerical quantities, and verify the final inequalities using exact rational arithmetic and interval arithmetic on a computer, ensuring there are no rounding errors. The result pushes the known boundary for the conjecture significantly, though closing the gap down to the conjectured threshold of maximum degree 9 remains an open problem.