A Note on Fractional DP-Coloring of Graphs

arXiv1910.03416MaRDI QIDQ6503887FDOQ6503887

Authors: Daniel Dominik, Hemanshu Kaul, J. A. Mudrock 

Abstract: DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvov{r}'{a}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 $ch{i}_{DP}^{\ast }(G)$, can be arbitrarily larger than $ch{i}^{\ast }(G)$, the graph's fractional chromatic number. In this note we show that for any $ngeq2$ and $minmathbbN$, there is a $tinmathbbN$ such that $ch{i}_{DP}^{\ast }(K_{n,m})leqn+1-1/t$, and we determine a lower bound on $ch{i}_{DP}^{\ast }(K_{2,m})$ for any $mgeq3$. We also generalize a result of Alon, Tuza, and Voigt, and in the process, show that for each $kinmathbbN$, $ch{i}_{DP}^{\ast }(C_{2k+1})=ch{i}^{\ast }(C_{2k+1})$.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: A Note on Fractional DP-Coloring of Graphs

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