Name
Abstract | ||
|---|---|---|
DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvorak and Postle [J. Combin. Theory Ser. B 129 (2018), pp. 38-54]. In this paper we introduce and study the fractional DP-chromatic number chi DP*(G). We characterize all connected graphs G such that chi DP*(G)<= 2: 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 chi l*(G) of any graph G equals its fractional chromatic number chi*(G). This equality does not extend to fractional DP-colorings. Moreover, we show that the difference chi DP*(G)-chi*(G) can be arbitrarily large, and, furthermore, chi DP*(G)> d/(2lnd) for every graph G of maximum average degree d > 4. 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/jgt.22482 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
d-degenerate graph,DP-coloring,fractional coloring | Graph,Combinatorics,Fractional coloring,Mathematics | Journal |
Volume | Issue | ISSN |
93.0 | 2.0 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anton Bernshteyn | 1 | 21 | 3.37 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Xuding Zhu | 3 | 1883 | 190.19 |