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 ${\chi }_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 ${\chi }_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.

18 pages plus references