Asymptotics for Palette Sparsification from Variable Lists

Abstract

It is shown that the following holds for each $\epsilon >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+\epsilon )\ln n$)-subsets of $S_v$ (independent of other choices), \[ \mbox{$G$ admits a proper coloring $\ddot{I}ƒ$ with $\ddot{I}{ƒ}_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.

37 pages, 0 figures. arXiv admin note: text overlap with arXiv:2306.00171