DP-Coloring of Graphs from Random Covers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915142386581504 |
|---|---|
| author | Bernshteyn, Anton Dominik, Daniel Kaul, Hemanshu Mudrock, Jeffrey A. |
| author_facet | Bernshteyn, Anton Dominik, Daniel Kaul, Hemanshu Mudrock, Jeffrey A. |
| contents | 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 $ρ\to\infty$ where $ρ$ is the maximum density of a graph: graphs are non-DP-colorable with high probability when $k$ is sufficiently smaller than $ρ/\lnρ$, and graphs are DP-colorable with high probability when $k$ is sufficiently larger than $ρ/\lnρ$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_13742 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | DP-Coloring of Graphs from Random Covers Bernshteyn, Anton Dominik, Daniel Kaul, Hemanshu Mudrock, Jeffrey A. Combinatorics Probability 05C15 (Primary) 05C69, 05C80 (Secondary) 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 $ρ\to\infty$ where $ρ$ is the maximum density of a graph: graphs are non-DP-colorable with high probability when $k$ is sufficiently smaller than $ρ/\lnρ$, and graphs are DP-colorable with high probability when $k$ is sufficiently larger than $ρ/\lnρ$. 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. |
| title | DP-Coloring of Graphs from Random Covers |
| topic | Combinatorics Probability 05C15 (Primary) 05C69, 05C80 (Secondary) |
| url | https://arxiv.org/abs/2308.13742 |