Fractional DP-colorings of sparse graphs

DOI10.1002/JGT.22482MaRDI QIDQ5110652zbMATH OpenOpenAlexWikidataFDO

Authors Anton Bernshteyn, Xuding Zhu, Alexandr Kostochka

Publication date 21 May 2020

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.07307

zbMATH Keywords

\(d\)-degenerate graphDP-coloringfractional coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvov{r}'{a}k and Postle. In this paper we introduce and study the fractional DP-chromatic number $ch{i}_{DP}^{a}st(G)$. We characterize all connected graphs $G$ such that $ch{i}_{DP}^{a}st(G)leqslant2$: they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt, the fractional list-chromatic number $ch{i}_{e}l{l}^{a}st(G)$ of any graph $G$ equals its fractional chromatic number $ch{i}^{a}st(G)$. This equality does not extend to fractional DP-colorings. Moreover, we show that the difference $ch{i}^{a}s{t}_{DP}(G)-ch{i}^{a}st(G)$ can be arbitrarily large, and, furthermore, $ch{i}^{a}s{t}_{DP}(G)geqd/(2lnd)$ for every graph $G$ of maximum average degree $dgeq4$. On the other hand, we show that this asymptotic lower bound is tight for a large class of graphs that includes all bipartite graphs as well as many graphs of high girth and high chromatic number.

Recommendations

• DP-colorings of graphs with high chromatic number
• Defective DP-colorings of sparse simple graphs
• Defective DP-colorings of sparse multigraphs
• A note on the DP-chromatic number of complete bipartite graphs
• On DP-coloring of graphs and multigraphs

Cited in

(16)

• A note on the DP-chromatic number of complete bipartite graphs
• Cover and variable degeneracy
• Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles
• On 2-defective DP-colorings of sparse graphs
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs
• DP-colorings of graphs with high chromatic number
• The asymptotic behavior of the correspondence chromatic number
• Partial DP-coloring of graphs
• Cooperative colorings of forests
• Relation between the correspondence chromatic number and the Alon-Tarsi number
• Fractional DP-chromatic number of planar graphs of large girth
• Fractional path coloring in bounded degree trees with applications
• Variable degeneracy on toroidal graphs
• A note on fractional DP-coloring of graphs
• DP-coloring of graphs from random covers

This page was built for publication: Fractional DP-colorings of sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5110652)