Article ID Journal Published Year Pages File Type
8902835 Discrete Mathematics 2018 4 Pages PDF
Abstract
DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvořák and Postle. Several known bounds for the list chromatic number of a graph G, χℓ(G), also hold for the DP-chromatic number of G, χDP(G). On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that χℓ(Kk,t)=k+1 if and only if t≥kk. We show that χDP(Kk,t)=k+1 if t≥1+(kk∕k!)(log(k!)+1), and we show that χDP(Kk,t)
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,