2019/10/04 by Dominik, Daniel, Kaul, Hemanshu, Mudrock, Jeffrey A.
#05C15 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1910.03416
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 χ_DP^*(G), can be arbitrarily larger than χ^*(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 ∈ ℕ, χ_DP^*(C2k+1) = χ^*(C2k+1). We also show that for any n ≥ 2 and m ∈ ℕ, if p^* is the solution in (0,1) to p=(1-p)n then χ_DP^*(Kn,m)≤1/p^*, and we prove a generalization of this result for multipartite graphs. Finally, we determine a lower bound on χ_DP^*(K2,m) for any m ≥ 3.