Martinsson-Steiner Conjecture on Fractional Chromatic Number
Is the fractional chromatic number of every -degenerate triangle-free graph at most , with a matching lower bound, as conjectured by Martinsson and Steiner? The upper bound is confirmed constructively for graphs of girth at least , and the conjectured lower bound is established in a stronger form for every fixed girth; the original triangle-free case remains open.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Graph coloring
- Posed by
- Anders Martinsson, Raphael Steiner
- Year posed
- —
- Years open
- —
- Solved
- 2026-07-28
- Model
- ChatGPT 5.5 Pro
- Vendor
- OpenAI
- Collaborators
- Peter Allen, Abhishek Dhawan, Jonathan A. Noel
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
girth >= 5 case; the triangle-free case remains open
What the AI did
The model solved an optimization problem the authors formulated to determine the correct shape of the fractional clique function, checked and simplified probabilistic and algebraic estimates, helped draft some calculations, and pointed the authors to a key reference. The construction and overall strategy are the authors', who take full responsibility.
Verification
arXiv preprint; not yet peer-reviewed.