Abstract:
We show that the following holds for each ε>0. For G an n-vertex graph of maximum degree D, lists Sv (v∈V(G)), and Lv chosen uniformly from the subsets of Sv of size (1+ε)lnn (independent of other choices), P(G admits a proper coloring σ with σv∈Lv ∀v)→1(as D→∞). When each Sv={1,…,D+1} ∀v, this is an asymptotically optimal version of the ``palette sparsification'' theorem of Assadi, Chen and Khanna. Joint with Charles Kenney.