Fractional DP‐colorings of sparse graphs
Anton Bernshteyn, Alexandr V. Kostochka, Xuding Zhu · Journal of Graph Theory · 2019
Abstract DP‐coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle [J. Combin. Theory Ser. B 129 (2018), pp. 38–54]. In this paper we introduce and study the fractional DP‐chromatic number . We characterize all connected graphs such that : they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt [Discrete Math. 165–166 (1997), pp. 31–38], the fractional list‐chromatic number of any graph equals its fractional chromatic number . This equality does not extend to fractional DP‐colorings. Moreover, we show that the difference can be arbitrarily large, and, furthermore, for every graph of maximum average degree . 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.