Borodin–Kostochka conjecture claimed for maximum degree ≥ 4583, with GPT-6 Astra assisting
Awaiting review
The takeaway
A preprint posted on Zenodo on Oct 20, 2026 by Lizhong Chen (HKUST) claims the Borodin–Kostochka conjecture (1977) for every graph of maximum degree Δ ≥ 4583: χ ≤ max{ω, Δ − 1}.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 20 October 2026
Your AI and this story
- GPT-6 Astra173 days after its cutoff
- Claude Opus 5.5112 days after its cutoff
- Gemini 4 Argon203 days after its cutoff
- Grok 4.7142 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 112 days before it.
Key facts
- Conjecture (Borodin & Kostochka, JCTB 1977): every graph with Δ ≥ 9 has χ ≤ max{ω, Δ − 1}, one colour fewer than Brooks’s theorem when there is no clique of size Δ
- Earlier: Reed proved it for sufficiently large Δ (JCTB 1999); Liu, Sun, Wang and Zeng gave the explicit threshold 5.3 × 10⁶ (arXiv 2603.16670, v3 May 2026); Chen’s own SSRN working manuscript had 2.9 × 10⁶
- New claim: Δ ≥ 4583, about a thousandfold lower; method: clique/sparse decomposition, random partial colouring with pre-selected families of witness triples, two applications of the local lemma, finite exponential-moment bounds
- The numerical part checks finitely many scalar inequalities in exact rational arithmetic (no graph enumeration); programs, parameters and reference output accompany the paper
- Disclosure (verbatim): ‘OpenAI GPT-6 Astra assisted with the resampling estimates in Section 6.4, moment-bound optimisation in Sections 7.3 and 8.1, weighted selection and local-lemma parameter choices in Sections 5 and 9, and the small-deficit constructions in Appendix A.3.’
- Single author; ~22,800-word PDF; no Lean formalisation; no expert reaction found on Oct 20
What happened
The paper does not settle the conjecture, but it claims to move the explicit bound from millions to a few thousand. The AI’s role is stated precisely in the paper’s own declaration (above). It was posted on Zenodo, not arXiv, and found through the sweep’s Zenodo step; its PDF was read for the disclosure.
Why it matters
It is another case of a frontier model credited with the technical estimate-tuning in a probabilistic combinatorics proof on a named 1977 conjecture. Like other single-author Zenodo claims, it needs expert checking before it counts.
What is disputed or not yet verified
| Verification | Unrefereed Zenodo preprint; rational-arithmetic checks with published code; not peer-reviewed or formalised |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed (Zenodo; PDF read with pdftotext)