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\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