PreprintarXiv licencearXiv
The Borodin--Kostochka inequality from degree 750
Abstract
We prove that every finite simple graph G with maximum degree at least $750$ satisfies χ(G)≤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 estimates handle the remaining vertices. The final probability inequalities are verified by directed rational and interval arithmetic.
Versions
Related
- The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs
- A Two-regime Khintchine Inequality and an Improved Bound on the Degree-1 Fourier Weight for Linear Threshold Functions
- On Borodin-Gorin presentation of Heckman-Opdam gln hypergeometric function
- Analytical Evaluation of Ramanujan Series for 1/π via Degree-2, Degree-3, Degree-7, and Degree-19 Modular Transformations
- Hilbert schemes of low-degree rational curves on a prime Fano threefold of degree $22$
BibTeX
@misc{chen2026borodinkostochka,
title = {{The Borodin--Kostochka inequality from degree 750}},
author = {Lizhong Chen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05423},
eprint = {2611.05423},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05423},
}
RIS
TY - UNPB
TI - The Borodin--Kostochka inequality from degree 750
AU - Lizhong Chen
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.05423
UR - https://arxiv.org/abs/2611.05423
AB - We prove that every finite simple graph G with maximum degree at least $750$ satisfies χ(G)≤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 estimates handle the remaining vertices. The final probability inequalities are verified by directed rational and interval arithmetic.
ER -