Graph Theory and Combinatorics Seminar

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

Abstract: Martinsson and Steiner recently showed that every $d$-degenerate triangle-free graph $G$ has fractional chromatic number $\chi_f(G) = O(d/\log d)$, and conjectured that the optimal bound is $(1+o(1))d/\log d$. We confirm the upper bound of this conjecture for graphs of girth at least $5$. Our proof also yields an efficient algorithm for sampling independent sets in such graphs, which is of independent interest.

We also prove the matching lower bound in a stronger form: for every fixed $g \ge 4$, there exist $d$-degenerate graphs $G$ of girth at least $g$ with $\chi_f(G) \ge (1-o(1))d/\log d$. Our construction is a random graph based on the uniform attachment model. Erd\H{o}s--R\'enyi random graphs have a conjectured factor-$2$ algorithmic gap for this problem. Our analysis shows that the uniform attachment model has no such computational barrier.

This talk is based on joint work with Peter Allen and Jonathan A. Noel.