Discrete Applied Mathematics Seminar by Daniel Dominik: DP-Coloring of Graphs from Random Covers

Speaker:  Daniel Dominik, Illinois Institute of Technology

Title:  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\v{r}\'{a}k and Postle in $2015$. DP-coloring of a graph $G$ is equivalent to an independent transversal of a DP-cover of $G$. Intuitively, a $k$-fold DP-cover of a graph $G$ is an assignment of lists of size $k$ to the vertices of $G$ where the names of colors vary from edge to edge. In this talk, 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 that give evidence towards the following threshold behavior on random $k$-fold DP-covers as $\rho \to \mathrm{\infty }$ where $\rho$ is the maximum density of a graph: graphs are non-DP-colorable with high probability when $k$ is sufficiently smaller than $\rho /\ln \rho$, and graphs are DP-colorable with high probability when $k$ is sufficiently larger than $\rho /\ln \rho$. Our results are dependent on $\rho$ growing fast enough and imply a sharp threshold for dense enough graphs. We study the threshold of sparse graphs in terms of their degeneracies. We also prove fractional DP-coloring analogs to these results. This is joint work with Anton Bernshteyn, Hemanshu Kaul, and Jeffrey A. Mudrock.

Discrete Applied Math Seminar

Request Zoom link