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 $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 $\ddot{I}\to \infty$ where $\ddot{I}$ is the maximum density of a graph: graphs are non-DP-colorable with high probability when $k$ is sufficiently smaller than $\ddot{I}/\ln \ddot{I}$, and graphs are DP-colorable with high probability when $k$ is sufficiently larger than $\ddot{I}/\ln \ddot{I}$. Our results depend on $\ddot{I}$ 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.

19 pages