Asymptotics for Palette Sparsification from Variable Lists

Jeff Kahn, Charles Kenney

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 uni…