A Note on Fractional DP-Coloring of Graphs

Abstract

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. In 2019, Bernshteyn, Kostochka, and Zhu introduced a fractional version of DP-coloring. They showed that unlike the fractional list chromatic number, the fractional DP-chromatic number of a graph $G$, denoted $\ddot{I}{‡}_{{}_{DP}}^{\ast }(G)$, can be arbitrarily larger than $\ddot{I}{‡}^{\ast }(G)$, the graph's fractional chromatic number. We generalize a result of Alon, Tuza, and Voigt (1997) on the fractional list chromatic number of odd cycles, and, in the process, show that for each $k\in \mathbb{N}$, $\ddot{I}{‡}_{{}_{DP}}^{\ast }(C_{2k+1})=\ddot{I}{‡}^{\ast }(C_{2k+1})$. We also show that for any $n\ge 2$ and $m\in \mathbb{N}$, if $p^{\ast }$ is the solution in $(0,1)$ to $p=(1-p{)}^n$ then $\ddot{I}{‡}_{{}_{DP}}^{\ast }(K_{n,m})\le 1/p^{\ast }$, and we prove a generalization of this result for multipartite graphs. Finally, we determine a lower bound on $\ddot{I}{‡}_{{}_{DP}}^{\ast }(K_{2,m})$ for any $m\ge 3$.

13 pages. arXiv admin note: text overlap with arXiv:1904.07697