Asymptotics for Palette Sparsification
| Autor: | Kahn, Jeff, Kenney, Charles |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | It is shown that the following holds for each $\varepsilon>0$. For $G$ an $n$-vertex graph of maximum degree $D$ and "lists" $L_v$ ($v \in V(G)$) chosen independently and uniformly from the ($(1+\varepsilon)\ln n$)-subsets of $\{1, ..., D+1\}$, \[ G \text{ admits a proper coloring } \sigma \text{ with } \sigma_v \in L_v \forall v \] with probability tending to 1 as $D \to \infty$. This is an asymptotically optimal version of a recent "palette sparsification" theorem of Assadi, Chen, and Khanna. Comment: 29 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|