2023/08/26 by Bernshteyn, Anton, Dominik, Daniel, Kaul, Hemanshu +1
#05C15 (Primary) 05C69 #05C80 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2308.13742
DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in 2015. Intuitively, DP-coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP-coloring of a graph G is equivalent to an independent transversal in an auxiliary structure called a DP-cover of G. In this paper, we introduce the notion of random DP-covers and study the behavior of DP-coloring from such random covers. We prove a series of results about the probability that a graph is or is not DP-colorable from a random cover. These results support the following threshold behavior on random k-fold DP-covers as ρ→∞ where ρ is the maximum density of a graph: graphs are non-DP-colorable with high probability when k is sufficiently smaller than ρ/lnρ, and graphs are DP-colorable with high probability when k is sufficiently larger than ρ/lnρ. Our results depend on ρ growing fast enough and imply a sharp threshold for dense enough graphs. For sparser graphs, we analyze DP-colorability in terms of degeneracy. We also prove fractional DP-coloring analogs to these results.