Open Research Index

On the Borodin--Kostochka conjecture for graphs with large maximum degree

Feng Liu, Shuang Sun, Yan Wang, Jiasheng Zeng

arXivarxiv/2603.16670Mar 17, 2026math.COscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2603.16670
curl -X POST /api/v1/records/arxiv/2603.16670/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.16670/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'