Sub-linear χ_f for K_r-free degenerate graphs
Problem 6.4 · arXiv:2601.15245
Status open high confidence
Problem 6.4 asks whether the maximum fractional chromatic number of K_r-free d-degenerate graphs is o_r(d) for each fixed r>=4. The source paper itself provides a lower bound of Omega_r(d/log^(r-2) d) via Theorem 1.6, which approaches linear in d as r grows, but no matching or sublinear upper bound is known for any r>=4. No follow-up paper resolving this question was found in the literature published after January 2026.
Reviewer notes. The r=3 (triangle-free) analogue was settled before this paper by arXiv:2501.18238, which proves an upper bound of (4+o(1))d/ln(d). Problem 6.4 concerns r>=4 only, where the question of sublinearity remains fully open. The paper arXiv:2603.17730 ('Fractional coloring via entropy', March 2026) proves bounds for locally r-colorable graphs and r-uniform hypergraphs but does not address K_r-free d-degenerate graphs and is not a follow-up to Problem 6.4.
Context
Theorem 1.6 gives a lower bound of $\Omega(d/\log^{(r-2)}d)$ on the fractional chromatic number of $K_r$-free $d$-degenerate graphs, which approaches linear in $d$ as $r$ increases, leaving open whether the maximum is truly sub-linear for each fixed $r\geq 4$.
Source paper
Coloring small locally sparse degenerate graphs and related problems
Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang · 2026-01-21
https://arxiv.org/abs/2601.15245