The Borodin-Kostochka conjecture, posed in 1977, claims that every graph with maximum degree at least 9 and no clique of size equal to its maximum degree has chromatic number at most one less than its maximum degree. The conjecture has resisted proof for nearly fifty years in its original form — ordinary graph coloring. Dvořák, Kang, and Mikšaník prove it under correspondence coloring, a strictly stronger framework, for graphs with maximum degree at least 3 times 10 to the ninth.
Correspondence coloring — also called DP-coloring — generalizes list coloring by allowing the “forbidden” color pairings between adjacent vertices to vary arbitrarily. In list coloring, two adjacent vertices with the same color in their lists are always in conflict. In correspondence coloring, the conflict structure is a separate input: which color at vertex u conflicts with which color at vertex v is specified edge by edge. Every proper coloring is a proper list coloring is a proper correspondence coloring, but not the reverse. The framework is harder to color in, so proving the conjecture there proves it everywhere below.
The mechanism is counterintuitive. The additional generality of correspondence coloring — which makes the coloring problem harder — simultaneously makes the proof tractable. The correspondence framework provides algebraic and structural leverage that ordinary coloring conceals. The proof uses a probabilistic argument with local recoloring, and the correspondence structure allows the recoloring to operate on each edge's conflict independently, avoiding the global dependencies that make the ordinary coloring case rigid.
The threshold of 3 times 10 to the ninth is large, far from the conjectured 9. But the point is not the constant — it's the method. The strongest version of the conjecture fell first. Sometimes a harder problem is a better-posed problem — the additional structure that makes it harder to solve also makes it easier to prove.