Metraipolis › archive › dc_049fed3741cd
Fractional DP-colorings of $d$-degenerate locally sparse graphs — arXiv:2609.10978
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10978
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T06:13:46.220Z
- SHA-256 of the archived text
a6342f5a1b5b86fef001362734d659e8e770519de1e448017f1131494e4ca596- Stable URL of this page
https://metraipolis.com/documento/dc_049fed3741cd
How to cite
Fractional DP-colorings of $d$-degenerate locally sparse graphs — arXiv:2609.10978 — arXiv (en), https://arxiv.org/abs/2609.10978 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_049fed3741cd (Metraipolis archive dc_049fed3741cd, sha256 a6342f5a1b5b86fef001362734d659e8e770519de1e448017f1131494e4ca596)
BibTeX
@misc{dc049fed3741cd,
title = {Fractional DP-colorings of $d$-degenerate locally sparse graphs — arXiv:2609.10978},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10978},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_049fed3741cd; sha256 a6342f5a1b5b86fef001362734d659e8e770519de1e448017f1131494e4ca596},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10978. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\chi_f^{\mathrm{DP}} \le (1 + o(1))\frac{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 $\chi_f^{\mathrm{DP}} \le (4 + o(1))\frac{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 $\frac{d^2}{f}$-locally-sparse, then \[ \chi_f^{\mathrm{DP}}(G) \le (8 + o(1))\frac{d}{\log f}. \] This immediately yields an identical upper bound on the ordinary fractional chromatic number $\chi_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 \ll f \le d^2$, we construct $d$-degenerate graphs that are left $\frac{d^2}{f}$-locally-sparse and satisfy $\chi_f(G) \ge (1 - o(1))\frac{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 $\Delta$. Notably, these bounds improve upon existing results even in the setting of ordinary fractional coloring.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-11 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.10978 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T05:59:08.294Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).