3-colorable graphs: O(n^0.1537) colors with GPT-6 Astra
Awaiting review
Importance: major (4 of 5)The takeaway
Ken-ichi Kawarabayashi, Kaisei Deguchi, Hirotaka Yoneda and Masataka Yoneda (NII / University of Tokyo) give a polynomial-time algorithm that colors any 3-colorable graph with O(n^0.1537) colors. The previous best was O(n^0.1954) (Bansal–Huang–Lee, SODA ‘27). By the paper’s account, GPT-6 Astra and GPT-6 Pro generated each intermediate algorithm (n^0.1736, n^0.1712, n^(1/6+ε), n^0.16, then n^0.1537), with the authors suggesting ideas and simplifying the analyses. The humans wrote the text.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 27 October 2026
Your AI and this story
- GPT-6 Astra179 days after its cutoff
- Claude Opus 5.5118 days after its cutoff
- Gemini 4 Argon209 days after its cutoff
- Grok 4.7148 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 118 days before it.
Key facts
- Authors: Ken-ichi Kawarabayashi (National Institute of Informatics & University of Tokyo), Kaisei Deguchi, Hirotaka Yoneda, Masataka Yoneda (University of Tokyo)
- Result: O(n^0.1537) colors for 3-colorable graphs in randomized polynomial time; previous O(n^0.1954) (Bansal–Huang–Lee, SODA ‘27); before that Õ(n^0.19747) (Kawarabayashi–Thorup–Yoneda, STOC 2024). The problem goes back to Wigderson’s O(√n) (1982), Blum, and the Karger–Motwani–Sudan SDP approach
- AI disclosure (verbatim): ‘Initially, GPT-6 Astra generated an O(n^0.1736)-coloring algorithm. Then, we studied the analysis and explicitly suggested an idea to GPT-6 Pro, which developed it into an O(n^0.1712)-coloring algorithm. Building on this approach, GPT-6 Astra developed an O(n^(1/6+ε))-coloring algorithm. Subsequently, the authors generalized the strict vector 3-coloring algorithm to ordinary vector k-coloring … and with these hints, GPT-6 Astra generated an O(n^0.16)-coloring algorithm. We iteratively simplified its analysis, and GPT-6 Astra improved the simplified algorithm. Finally, GPT-6 Astra generated the final O(n^0.1537)-color algorithm.’
- Writing: ‘This paper is entirely written by the human authors. However, we used GPT-5.6 Sol, GPT-6 Sol, GPT-6 Astra, and Claude Opus 5.5 to polish the presentation of the paper. Finally, the authors take full responsibility for the correctness and content of the paper.’
- Status: unrefereed arXiv preprint, no formalization; no public reaction found on 27 Oct
What happened
Every 3-colorable graph can be colored with three colors, but finding such a coloring is NP-hard, so algorithms settle for more colors. The record has been a power of n that crept down slowly: O(√n) in 1982, then Blum’s combinatorial methods and semidefinite programming. Kawarabayashi, Thorup and Yoneda reached n^0.19747 in 2024, and Bansal, Huang and Lee n^0.1954 in a SODA ‘27 paper.
The new paper jumps to n^0.1537. Its AI disclosure describes the work as a relay: GPT-6 Astra produced an n^0.1736 algorithm, GPT-6 Pro improved it to n^0.1712 after a hint from the authors, Astra reached n^(1/6+ε), and after the authors generalized one ingredient, Astra produced n^0.16 and finally n^0.1537. The authors studied and simplified each analysis and wrote the paper.
Why it matters
This is a well-known benchmark problem in approximation algorithms, and the improvement is large by its standards. The disclosure is unusually specific about which system produced each algorithm. It shows a working pattern in which the models propose algorithms and the experts steer and verify. The result is unrefereed.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint |
|---|
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed (science agent; arXiv cs.DS listing of 27 Oct, PDF read with pdftotext)