Processing math: 100%

ACO The ACO Seminar (2023–2024)

March 21, 3:00pm, Wean 8220
Jeff Kahn, Rutgers University
Asymptotics for palette sparsification

Abstract:

We show that the following holds for each ε>0. For G an n-vertex graph of maximum degree D, lists Sv (vV(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 σvLv 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.


Back to the ACO home page Back to the ACO Seminar schedule