DP‐Coloring of Graphs From Random Covers

ABSTRACT 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 is equivalent to an independent transversal in an auxiliary structure called a DP‐cover of . 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 ‐fold DP‐covers as where is the maximum density of a graph: Graphs are non‐DP‐colorable with high‐probability when is sufficiently smaller than , and graphs are DP‐colorable with high‐probability when is sufficiently larger than . 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.