Asymptotics for Palette Sparsification

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$ and "lists" $L_v$ ($v\in V(G)$) chosen independently and uniformly…