A Note on the DP-Chromatic Number of Complete Bipartite Graphs

2018/03/24 by Mudrock, Jeffrey A.
#05C15 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1803.09141

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 shows that it differs with the list chromatic number. In this note we show one such property. It is well known that χ_ℓ (K_k,t) = k+1 if and only if t ≥ k^k. We show that χ_DP (K_k,t) = k+1 if t ≥ 1 + (k^k/k!)(log(k!)+1), and we show that χ_DP (K_k,t) < k+1 if t < k^k/k!.

Related

• On differences between DP-coloring and list coloring
• DP-Coloring Cartesian Products of Graphs
• On the Chromatic Polynomial and Counting DP-Colorings
• On the DP-chromatic Number of Cartesian Products of Critical Graphs
• A Note on Fractional DP-Coloring of Graphs