Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.07928 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929693366681600 |
|---|---|
| author | Kahn, Jeff Kenney, Charles |
| author_facet | Kahn, Jeff Kenney, Charles |
| contents | It is shown that the following holds for each $\varepsilon >0$. For $G$ an $n$-vertex graph of maximum degree $D$, lists $S_v$ of size $D+1$ (for $v\in V(G)$), and $L_v$ chosen uniformly from the ($(1+\varepsilon)\ln n$)-subsets of $S_v$ (independent of other choices), \[ \mbox{$G$ admits a proper coloring $σ$ with $σ_v\in L_v$ $\forall v$} \] with probability tending to 1 as $D\to \infty$.
When each $S_v $ is $\{1\dots D+1\}$, this is an asymptotically optimal version of the ``palette sparsification'' theorem of Assadi, Chen and Khanna that was proved in an earlier paper by the present authors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07928 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotics for Palette Sparsification from Variable Lists Kahn, Jeff Kenney, Charles Combinatorics 05C15 It is shown that the following holds for each $\varepsilon >0$. For $G$ an $n$-vertex graph of maximum degree $D$, lists $S_v$ of size $D+1$ (for $v\in V(G)$), and $L_v$ chosen uniformly from the ($(1+\varepsilon)\ln n$)-subsets of $S_v$ (independent of other choices), \[ \mbox{$G$ admits a proper coloring $σ$ with $σ_v\in L_v$ $\forall v$} \] with probability tending to 1 as $D\to \infty$. When each $S_v $ is $\{1\dots D+1\}$, this is an asymptotically optimal version of the ``palette sparsification'' theorem of Assadi, Chen and Khanna that was proved in an earlier paper by the present authors. |
| title | Asymptotics for Palette Sparsification from Variable Lists |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2407.07928 |