The Borodin--Kostochka inequality from degree 750
Source: arxiv.org/abs/2611.05423
We prove that every finite simple graph $G$ with maximum degree at least $750$ satisfies $χ(G)\le\max\{ω(G),Δ(G)-1\}$. The proof starts with a random partial colouring and completes it on large cliques using a list-colouring condition that remains valid as the rest of the graph is coloured. Disjoint stars provide the required colours. We estimate the number of stars that can be chosen after the clique colours have been exposed, while keeping their endpoint set fixed. A common exponential-moment argument reduces intervals of packing sizes to endpoint comparisons. More detailed neighbourhood…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05423
curl -X POST /api/v1/records/arxiv/2611.05423/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05423/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'