---
id: "2026-10-26-three-coloring-n-0-1537-gpt-6-astra"
url: "https://postcutoff.com/e/2026-10-26-three-coloring-n-0-1537-gpt-6-astra/"
as_of: "2026-10-30T13:42:00+01:00"
date: "2026-10-26"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Preprint only
sources: 2
editor: human editor
human_review: null
version: "2026-10-27"
---

As of: 2026-10-30 13:42 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-10-26-three-coloring-n-0-1537-gpt-6-astra/

# 3-colorable graphs: O(n^0.1537) colors with GPT-6 Astra

Full title: Coloring 3-colorable graphs with O(n^0.1537) colors, down from n^0.1954: Kawarabayashi and co-authors say GPT-6 Astra and GPT-6 Pro generated the successive algorithms

arXiv 2610.35859 (cs.DS, 26 Oct 2026): a randomized polynomial-time algorithm colors every n-vertex 3-colorable graph with O(n^0.1537) colors, improving O(n^0.1954) (Bansal, Huang, Lee, SODA '27). It finds large independent sets from vector-coloring SDP solutions, combined with the Kawarabayashi–Thorup–Yoneda dense-progress algorithm, which gives n^(1/6+o(1)), and then a strengthened SDP algorithm for the 0.1537 exponent. The AI disclosure describes a chain of model-generated algorithms, with human hints in between.

## 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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 179 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 118 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 209 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 148 days after its cutoff

## Sources

1. [arXiv 2610.35859: An O(n^0.1537)-Coloring Algorithm for 3-Colorable Graphs](https://arxiv.org/abs/2610.35859) (arxiv.org, paper)
2. [Kawarabayashi, Thorup, Yoneda (STOC 2024): Better coloring of 3-colorable graphs (arXiv 2406.00357)](https://arxiv.org/abs/2406.00357) (arxiv.org, paper)

## Changes

- 2026-10-27 (filed): Created (science agent; arXiv cs.DS listing of 27 Oct, PDF read with pdftotext)

## Related

- 2026-10-27: [AI-assisted results in the 27 Oct 2026 sweep](https://postcutoff.com/e/2026-10-27-ai-assisted-results-october-27-listing/index.md)