Fractional DP-colorings of d-degenerate locally sparse graphs
Abstract
Bernshteyn, Kostochka, and Zhu (2020) introduced the notion of fractional DP-coloring, which generalizes both fractional coloring and fractional list coloring. Among several foundational results, they proved that every d-degenerate bipartite graph G satisfies χfDP ≤ (1 + o(1))d/(log d), and that this bound is optimal---a stark contrast to ordinary fractional coloring. In this paper, we extend this upper bound to all d-degenerate triangle-free graphs, proving that χfDP ≤ (4 + o(1))d/(log d). This generalizes a recent result of Martinsson and Steiner (2025) for ordinary fractional coloring. We derive this result as a corollary of a more general upper bound concerning locally sparse graph orderings. Specifically, a d-degenerate graph G is left k-locally-sparse if it admits a degeneracy ordering in which, for every vertex v, the subgraph induced by its back-neighbors contains at most k edges. We show that if a d-degenerate graph G is left d2/f-locally-sparse, then χfDP(G) ≤ (8 + o(1))d/(log f). This immediately yields an identical upper bound on the ordinary fractional chromatic number χf(G), improving upon the leading constants of previously known bounds. Additionally, we establish the asymptotic sharpness of this result up to the leading constant. For any 1 ≪ f ≤ d2, we construct d-degenerate graphs that are left d2/f-locally-sparse and satisfy χf(G) ≥ (1 − o(1))d/(log f). Finally, as applications of our main theorem, we obtain improved upper bounds on the fractional DP-chromatic number of d-degenerate K1,t,t-free graphs, as well as Kt,t,t-free graphs with maximum degree Δ. Notably, these bounds improve upon existing results even in the setting of ordinary fractional coloring.
Related
- On strong odd colorings of sparse graphs
- Fractional colorings of Kr-free graphs with local demands
- Weighted odd-cycle transversals and fractional colorings of planar graphs
- Thresholds and Fluctuations for Colorful Arithmetic Progressions in Sparse Random Colorings
- Good stratifications of non-degenerate locally tame complete intersection varieties
BibTeX
@misc{dhawan2026fractional,
title = {{Fractional DP-colorings of $d$-degenerate locally sparse graphs}},
author = {Abhishek Dhawan and Huy Nguyen and Rohan A. Rathi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10978},
eprint = {2609.10978},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10978},
}
RIS
TY - UNPB
TI - Fractional DP-colorings of d-degenerate locally sparse graphs
AU - Abhishek Dhawan
AU - Huy Nguyen
AU - Rohan A. Rathi
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.10978
UR - https://arxiv.org/abs/2609.10978
AB - Bernshteyn, Kostochka, and Zhu (2020) introduced the notion of fractional DP-coloring, which generalizes both fractional coloring and fractional list coloring. Among several foundational results, they proved that every d-degenerate bipartite graph G satisfies χ_f^DP ≤ (1 + o(1))d/(log d), and that this bound is optimal---a stark contrast to ordinary fractional coloring. In this paper, we extend this upper bound to all d-degenerate triangle-free graphs, proving that χ_f^DP ≤ (4 + o(1))d/(log d). This generalizes a recent result of Martinsson and Steiner (2025) for ordinary fractional coloring. We derive this result as a corollary of a more general upper bound concerning locally sparse graph orderings. Specifically, a d-degenerate graph G is left k-locally-sparse if it admits a degeneracy ordering in which, for every vertex v, the subgraph induced by its back-neighbors contains at most k edges. We show that if a d-degenerate graph G is left d^2/f-locally-sparse, then χ_f^DP(G) ≤ (8 + o(1))d/(log f). This immediately yields an identical upper bound on the ordinary fractional chromatic number χ_f(G), improving upon the leading constants of previously known bounds. Additionally, we establish the asymptotic sharpness of this result up to the leading constant. For any 1 ≪ f ≤ d^2, we construct d-degenerate graphs that are left d^2/f-locally-sparse and satisfy χ_f(G) ≥ (1 − o(1))d/(log f). Finally, as applications of our main theorem, we obtain improved upper bounds on the fractional DP-chromatic number of d-degenerate K_1,t,t-free graphs, as well as K_t,t,t-free graphs with maximum degree Δ. Notably, these bounds improve upon existing results even in the setting of ordinary fractional coloring.
ER -