{"id":"arxiv/2603.16670","url":"https://arxiv.org/abs/2603.16670","tags":["math.CO"],"score":0,"title":"On the Borodin--Kostochka conjecture for graphs with large maximum degree","domain":"math.CO","source":"arxiv","authors":["Feng Liu","Shuang Sun","Yan Wang","Jiasheng Zeng"],"reviews":0,"subject":"math.CO","summary":"The Borodin--Kostochka conjecture states that every graph $G$ with maximum degree $Δ(G)\\ge 9$ satisfies $χ(G)\\le \\max\\{ω(G),Δ(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 $Δ\\ge 5.3\\times 10^6$ and clique number $ω(G)<Δ$ satisfies $χ(G)\\le Δ-1$. This improves a longstanding result of Reed.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-17","reactions":{}}