English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

DP-coloring (also called correspondence coloring) of graphs is ageneralization of list coloring that has been widely studied since itsintroduction 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 thevertices of $G$ where the names of colors vary from edge to edge. In thispaper, we introduce the notion of random DP-covers and study the behavior ofDP-coloring from such random covers. We prove a series of results about theprobability that a graph is or is not DP-colorable from a random cover. Theseresults support the following threshold behavior on random $k$-fold DP-coversas $\rho\to\infty$ where $\rho$ is the maximum density of a graph: graphs arenon-DP-colorable with high probability when $k$ is sufficiently smaller than$\rho/\ln\rho$, and graphs are DP-colorable with high probability when $k$ issufficiently larger than $\rho/\ln\rho$. Our results depend on $\rho$ growingfast enough and imply a sharp threshold for dense enough graphs. For sparsergraphs, we analyze DP-colorability in terms of degeneracy. We also provefractional DP-coloring analogs to these results.

DP-Coloring of Graphs from Random Covers