Fractional chromatic number of K_r-free d-degenerate graphs
Problem 4.1 · arXiv:2601.15245
Status open high confidence
Problem 4.1 asks for the maximum fractional chromatic number of a $d$-degenerate, $K_r$-free graph. The source paper itself establishes via Theorem 1.6 a lower bound of $\Omega_r(d/\log^{r-2} d)$, ruling out the $O_r(d\log\log d/\log d)$ bound one might expect by analogy with Johansson's theorem for bounded-degree $K_r$-free graphs. No subsequent paper resolving or settling the full question was found; the related paper arXiv:2603.17730 addresses fractional chromatic number of $d$-degenerate locally $r$-colorable graphs (a different condition from $K_r$-freeness) but does not settle Problem 4.1.
Cited literature (1)
-
Proves $\chi_f(G) = O(d\log(2r)/\log d)$ for $d$-degenerate locally $r$-colorable graphs using an entropy-based approach, addressing a related but distinct problem class from $K_r$-free $d$-degenerate graphs; does not directly resolve Problem 4.1.
Reviewer notes. Problem 4.1 is posed as an open question in January 2026. The source paper provides a lower bound $\Omega_r(d/\log^{r-2} d)$ via Theorem 1.6, showing the answer exceeds the natural $O_r(d\log\log d/\log d)$ analogy. No follow-up paper directly resolving the $K_r$-free case was found as of 2026-05-14.
Context
Given the main theorem of Martinsson [26] on triangle-free $d$-degenerate graphs and its many applications, the authors seek a generalization of Harris' conjecture for $K_{r}$-free graphs. One might guess the answer is $O_{r}\left(\frac{d\log\log d}{\log d}\right)$ by analogy with Johansson's bound for $K_r$-free graphs of maximum degree $\Delta$, but Theorem 1.6 shows this is not the case.
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