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

Feng Liu; Jiasheng Zeng; Shuang Sun; Yan Wang

arxiv: 2603.16670 · v3 · submitted 2026-03-17 · 🧮 math.CO

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

Feng Liu , Shuang Sun , Yan Wang , Jiasheng Zeng This is my paper

Pith reviewed 2026-05-15 10:04 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C15

keywords Borodin-Kostochka conjecturegraph coloringchromatic numbermaximum degreeclique numberReed's theorem

0 comments

The pith

Every graph with maximum degree at least 5.3 million and clique number less than the degree has chromatic number at most the degree minus one.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Borodin-Kostochka conjecture holds for all graphs whose maximum degree reaches or exceeds 5.3 times 10 to the sixth power. It shows that any such graph whose largest clique is smaller than its maximum degree can be properly colored with one fewer color than that degree. This lowers the degree threshold from Reed's earlier bound and verifies the conjecture once the maximum degree is large enough for the structural arguments to apply. A reader would care because the result closes the conjecture for all sufficiently high degrees, leaving only the finite range of smaller degrees as remaining cases.

Core claim

Every graph G with maximum degree Δ(G) ≥ 5.3×10^6 and clique number ω(G) < Δ(G) satisfies χ(G) ≤ Δ(G)−1.

What carries the argument

Structural analysis of minimal counterexamples, which becomes decisive once Δ is at least 5.3 million and thereby forces the desired (Δ−1)-coloring when no clique of size Δ exists.

If this is right

Graphs meeting the degree and clique conditions are (Δ−1)-colorable.
The Borodin-Kostochka conjecture holds for every graph whose maximum degree is at least 5.3 million.
Only graphs with maximum degree below 5.3 million remain open for the conjecture when the clique number is less than Δ.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same structural method might be sharpened to reduce the degree threshold further.
If the bound eventually reaches Δ = 9, the conjecture would be fully settled except for graphs containing a clique of size Δ.
Direct computation on random graphs with moderate Δ could indicate how far below 5.3 million the result actually holds.

Load-bearing premise

The maximum degree must be at least 5.3 million for the structural properties of minimal counterexamples to guarantee the coloring bound.

What would settle it

A single graph with maximum degree at least 5.3 million, no clique of size equal to that degree, yet chromatic number equal to the maximum degree would disprove the claim.

read the original abstract

The Borodin--Kostochka conjecture states that every graph $G$ with maximum degree $\Delta(G)\ge 9$ satisfies $\chi(G)\le \max\{\omega(G),\Delta(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 $\Delta \ge 5.3\times 10^6$ and clique number $\omega(G)<\Delta$ satisfies $\chi(G)\le \Delta-1$. This improves a longstanding result of Reed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper pins the Borodin-Kostochka conjecture down to an explicit threshold of Δ at least 5.3 million.

read the letter

The main point is that the authors prove every graph with maximum degree at least 5.3 million and clique number less than Δ has chromatic number at most Δ-1. This improves Reed's older result by replacing an unspecified large-enough bound with a concrete number that comes out of their estimates on minimal counterexamples. The structural work looks standard for these problems: they assume a smallest counterexample and show that large Δ forces enough slack in the neighborhoods to reach a contradiction or a reducible configuration. That part is done cleanly enough to produce the specific cutoff. The explicit constant is the real gain here, since it lets later papers cite a definite range rather than an existence statement. The obvious limitation is the size of the number itself. Five million is still enormous, so the result leaves the entire moderate-degree range open and does not move the needle on the original conjecture for Δ near 9. The proof must rely on Δ dominating various lower-order terms in the counting arguments, which works but also explains why the threshold sits so high. No internal contradictions or circular steps appear in the setup. This is aimed at people who follow degree conditions for coloring and want to track incremental progress on the conjecture. A reader writing a survey or trying to tighten bounds further would find the concrete figure useful. It deserves peer review to verify the details of how the estimates close at exactly that point.

Referee Report

0 major / 2 minor

Summary. The paper proves that the Borodin-Kostochka conjecture holds for graphs with sufficiently large maximum degree: every graph G with Δ(G) ≥ 5.3×10^6 and ω(G) < Δ satisfies χ(G) ≤ Δ-1. The argument proceeds by assuming a minimal counterexample and deriving a contradiction from structural properties that become controllable once Δ is large enough to dominate lower-order terms.

Significance. If the proof is correct, the result supplies an explicit (albeit large) threshold beyond which the conjecture is verified, improving Reed's earlier bound. The approach via minimal counterexamples and degree-controlled structural lemmas is standard in the area and yields a concrete, falsifiable statement that narrows the remaining open range for the conjecture.

minor comments (2)

[Abstract] The abstract and introduction should explicitly compare the new threshold 5.3×10^6 with the precise constant obtained by Reed, including a brief indication of which estimates were tightened.
[Main theorem section] In the proof of the main theorem, the dependence of the structural lemmas on the largeness of Δ should be summarized in a single displayed inequality or table so that the origin of the numerical threshold is transparent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of our manuscript. The report recommends minor revision but lists no specific major comments or requested changes. We are grateful for the recognition that the result improves Reed's bound with an explicit threshold and that the minimal-counterexample approach is standard in the area. Since no concrete points were raised for revision, we see no need for changes at this time but remain ready to address any minor issues the editor or referee may wish to specify.

Circularity Check

0 steps flagged

No significant circularity in derivation

full rationale

The paper establishes the stated bound via a direct structural proof on minimal counterexamples, using discharging and reducibility arguments that close for sufficiently large Δ. No equations reduce a claimed prediction to a fitted input by construction, no self-citation chain is load-bearing for the central claim, and the explicit threshold 5.3×10^6 arises from dominating lower-order terms rather than from re-labeling or self-definition. The argument improves an external result of Reed and remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard axioms of graph theory (definitions of χ, Δ, ω, and basic properties of minimal counterexamples) with no free parameters or new entities introduced in the abstract.

axioms (1)

standard math Standard definitions and basic properties of chromatic number, maximum degree, and clique number in simple graphs.
These are the foundational objects used in every statement of the Borodin-Kostochka conjecture.

pith-pipeline@v0.9.0 · 5394 in / 1190 out tokens · 66095 ms · 2026-05-15T10:04:10.281401+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.3: Every graph G with Δ(G) ≥ 5.2×10^9 satisfies χ(G) ≤ max{Δ(G)-1, ω(G)}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

Azuma, Weighted sums of certain dependent random variables,Tohoku Math

K. Azuma, Weighted sums of certain dependent random variables,Tohoku Math. J.19(1967), 357–367

work page 1967
[2]

O. V. Borodin and A. V. Kostochka, On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density,J. Combin. Theory Ser. B23(1977), 247–250

work page 1977
[3]

R. L. Brooks, On coloring the nodes of a network,Math. Proc. Cambridge Philos. Soc.37(1941), 194–197

work page 1941
[4]

P. A. Catlin,Embedding Subgraphs and Coloring Graphs under Extremal Degree Conditions, Ph.D. Thesis, The Ohio State University, 1976

work page 1976
[5]

R. Chen, K. Lan, X. Lin and Y. Zhou, Borodin–Kostochka conjecture holds for odd-hole-free graphs,Graphs Combin.40(2024), 26

work page 2024
[6]

R. Chen, K. Lan, X. Lin and Y. Zhou, The chromatic number of odd-hole-free graphs,Discrete Appl. Math.370(2025), 84–87. 16

work page 2025
[7]

R. Chen, K. Lan and Y. Zhou, Coloring{P2 ∪P 3,house}-free graphs with∆ − 1colors,Discrete Appl. Math.342(2024), 12–18

work page 2024
[8]

D. W. Cranston, H. Lafayette and L. Rabern, Coloring{P5,gem}-free graphs with∆ − 1colors, J. Graph Theory101(2022), 633–642

work page 2022
[9]

D. W. Cranston and L. Rabern, Coloring claw-free graphs with∆− 1colors,SIAM J. Discrete Math.27(2013), 534–549

work page 2013
[10]

D. W. Cranston and L. Rabern, Brooks’ theorem and beyond,J. Graph Theory80(2015), 199–225

work page 2015
[11]

Dvořák, R

Z. Dvořák, R. J. Kang and D. Mikšaník, On Borodin–Kostochka conjecture for correspondence coloring, arXiv:2603.14427, 2026

work page arXiv 2026
[12]

Erdős and L

P. Erdős and L. Lovász, Problems and results on3-chromatic hypergraphs and some related questions, in:Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North- Holland, Amsterdam, 1975, pp. 609–627

work page 1975
[13]

Galindo, T

R. Galindo, T. McDonald and C. Shan, Large cliques or high odd holes in graphs with chromatic number equal to maximum degree,Discrete Appl. Math.383(2026), 383–386

work page 2026
[14]

Gupta and D

S. Gupta and D. Pradhan, The Borodin–Kostochka conjecture for{P5, C4}-free graphs,Discrete Math.344(2021), 112233

work page 2021
[15]

A. V. Kostochka, Degree, density, and chromatic number,Metody Diskret. Anal.35(1980), 45–70

work page 1980
[16]

K. Lan, F. Liu and Y. Zhou, Borodin–Kostochka’s conjecture on{P2 ∪P 3, C4}-free graphs,Graphs Combin.40(2024), 123

work page 2024
[17]

R. A. Moser and G. Tardos, A constructive proof of the general Lovász Local Lemma,J. ACM 57(2010), Article 11

work page 2010
[18]

Reed, A strengthening of Brooks’ theorem,J

B. Reed, A strengthening of Brooks’ theorem,J. Combin. Theory Ser. B76(1999), 136–149

work page 1999
[19]

Wu and R

D. Wu and R. Wu, Borodin–Kostochka Conjecture for a Family ofP6-free Graphs,Acta Math. Appl. Sin. Engl. Ser.(2025). doi:10.1007/s10255-025-0059-9. 17

work page doi:10.1007/s10255-025-0059-9 2025

[1] [1]

Azuma, Weighted sums of certain dependent random variables,Tohoku Math

K. Azuma, Weighted sums of certain dependent random variables,Tohoku Math. J.19(1967), 357–367

work page 1967

[2] [2]

O. V. Borodin and A. V. Kostochka, On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density,J. Combin. Theory Ser. B23(1977), 247–250

work page 1977

[3] [3]

R. L. Brooks, On coloring the nodes of a network,Math. Proc. Cambridge Philos. Soc.37(1941), 194–197

work page 1941

[4] [4]

P. A. Catlin,Embedding Subgraphs and Coloring Graphs under Extremal Degree Conditions, Ph.D. Thesis, The Ohio State University, 1976

work page 1976

[5] [5]

R. Chen, K. Lan, X. Lin and Y. Zhou, Borodin–Kostochka conjecture holds for odd-hole-free graphs,Graphs Combin.40(2024), 26

work page 2024

[6] [6]

R. Chen, K. Lan, X. Lin and Y. Zhou, The chromatic number of odd-hole-free graphs,Discrete Appl. Math.370(2025), 84–87. 16

work page 2025

[7] [7]

R. Chen, K. Lan and Y. Zhou, Coloring{P2 ∪P 3,house}-free graphs with∆ − 1colors,Discrete Appl. Math.342(2024), 12–18

work page 2024

[8] [8]

D. W. Cranston, H. Lafayette and L. Rabern, Coloring{P5,gem}-free graphs with∆ − 1colors, J. Graph Theory101(2022), 633–642

work page 2022

[9] [9]

D. W. Cranston and L. Rabern, Coloring claw-free graphs with∆− 1colors,SIAM J. Discrete Math.27(2013), 534–549

work page 2013

[10] [10]

D. W. Cranston and L. Rabern, Brooks’ theorem and beyond,J. Graph Theory80(2015), 199–225

work page 2015

[11] [11]

Dvořák, R

Z. Dvořák, R. J. Kang and D. Mikšaník, On Borodin–Kostochka conjecture for correspondence coloring, arXiv:2603.14427, 2026

work page arXiv 2026

[12] [12]

Erdős and L

P. Erdős and L. Lovász, Problems and results on3-chromatic hypergraphs and some related questions, in:Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North- Holland, Amsterdam, 1975, pp. 609–627

work page 1975

[13] [13]

Galindo, T

R. Galindo, T. McDonald and C. Shan, Large cliques or high odd holes in graphs with chromatic number equal to maximum degree,Discrete Appl. Math.383(2026), 383–386

work page 2026

[14] [14]

Gupta and D

S. Gupta and D. Pradhan, The Borodin–Kostochka conjecture for{P5, C4}-free graphs,Discrete Math.344(2021), 112233

work page 2021

[15] [15]

A. V. Kostochka, Degree, density, and chromatic number,Metody Diskret. Anal.35(1980), 45–70

work page 1980

[16] [16]

K. Lan, F. Liu and Y. Zhou, Borodin–Kostochka’s conjecture on{P2 ∪P 3, C4}-free graphs,Graphs Combin.40(2024), 123

work page 2024

[17] [17]

R. A. Moser and G. Tardos, A constructive proof of the general Lovász Local Lemma,J. ACM 57(2010), Article 11

work page 2010

[18] [18]

Reed, A strengthening of Brooks’ theorem,J

B. Reed, A strengthening of Brooks’ theorem,J. Combin. Theory Ser. B76(1999), 136–149

work page 1999

[19] [19]

Wu and R

D. Wu and R. Wu, Borodin–Kostochka Conjecture for a Family ofP6-free Graphs,Acta Math. Appl. Sin. Engl. Ser.(2025). doi:10.1007/s10255-025-0059-9. 17

work page doi:10.1007/s10255-025-0059-9 2025