Fractional chromatic numbers of high-girth degenerate graphs

For fixed girth g≥4, how large can the fractional chromatic number of a d-degenerate graph be as d grows? The target lower scale is (1−o(1))d/log d, with leading constant one.

Why it matters and what counts as progress

Why it matters: It tests the sharp constant in the interaction between sparse degeneracy, large girth and fractional colouring.

What counts as progress: Construct high-girth d-degenerate graphs with larger fractional chromatic number, or prove matching upper bounds on the leading d/log d constant.

How the problem developed

2025 · Upper bound [1]
Anders Martinsson and Raphael Steiner Proved that triangle-free d-degenerate graphs have fractional chromatic number O(d/log d), and proposed a sharp leading constant of 1+o(1).
28 Jul 2026 · Reported theorem [2]
Peter Allen, Abhishek Dhawan and Jonathan A. Noel Proved the 1+o(1) upper bound for girth at least five and constructed matching lower-bound examples for every fixed girth at least four.

AI contribution

Sharp bounds for the fractional chromatic number of high-girth d-degenerate graphs

Peter Allen, Abhishek Dhawan, Jonathan A. Noel

Allen, Dhawan and Noel prove that for every fixed girth g≥4 there are d-degenerate graphs of girth at least g with fractional chromatic number at least (1−o(1))d/log d as d grows. ChatGPT solved the authors’ optimization problem for the fractional clique function used in this lower-bound proof.

AI involvementAI-centered

ImportanceNotable

Technical verificationReported

Human understandingFull