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 (Formula presented.). We characterize all connected graphs (Formula presented.) such that (Formula presented.) : 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 (Formula presented.) of any graph (Formula presented.) equals its fractional chromatic number (Formula presented.). This equality does not extend to fractional DP-colorings. Moreover, we show that the difference (Formula presented.) can be arbitrarily large, and, furthermore, (Formula presented.) for every graph (Formula presented.) of maximum average degree (Formula presented.). 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.
Original language | English (US) |
---|---|
Pages (from-to) | 203-221 |
Number of pages | 19 |
Journal | Journal of Graph Theory |
Volume | 93 |
Issue number | 2 |
DOIs | |
State | Published - Feb 1 2020 |
Keywords
- DP-coloring
- d-degenerate graph
- fractional coloring
ASJC Scopus subject areas
- Geometry and Topology