Asymptotics for Palette Sparsification from Variable Lists

It is shown that the following holds for each ε >0. For G an n-vertex graph of maximum degree D, lists Sᵥ (v∈ V(G)), and Lᵥ chosen uniformly from the ((1+ε)ln n)-subsets of Sᵥ (independent of other choices), \[ G admits a proper coloring σ with σᵥ∈ Lᵥ ∀ v \] with probability tending to 1 as D→ ∞. When each Sᵥ is \1 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.