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

Abstract

Martinsson and Steiner recently proved that the fractional chromatic number of any $d$-degenerate triangle-free graph $G$ satisfies $χ_f(G) = O\left(\frac{d}{\log d}\right)$. They further conjectured a sharp leading constant $1 + o(1)$. In this paper, we confirm their upper bound conjecture for graphs having girth at least $5$. Our proof is constructive: it gives an efficient randomized algorithm that, with high probability, computes a fractional coloring of weight at most $(1 + o(1))\frac{d}{\log d}$ in such graphs. Furthermore, we establish their conjectured lower bound in a stronger form: for any constant $g \ge 4$, there exist $d$-degenerate graphs having girth at least $g$ with $χ_f(G) \ge (1 - o(1))\frac{d}{\log d}$. This lower bound is achieved by analyzing a random graph based on the uniform attachment model. Notably, our results reveal that this model lacks the typical computational complexity barriers found in Erdős-Rényi graphs, where there is a conjectured factor-$2$ algorithmic gap for this problem.

Disclosure

“ef Skokan, and Evelyne Smith-Roberge for organizing the workshop and inviting us, and all of the participants for stimulating discussions. We also thank Seth Pettie for comments on an earlier version of this manuscript. The authors used ChatGPT 5.5 Pro to aid in the proof of Theorem 1.4. In particular, it was used to solve an optimization problem that the authors formulated to determine the correct shape of the fractional clique function, to check and simplify some probabilistic”

PDF page 18

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:11:15.754810Z

Structural counts