  A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19]
states that in every $n$-vertex graph $G$ with maximum degree $\Delta$,
sampling $O(\log{n})$ colors per each vertex independently from $\Delta+1$
colors almost certainly allows for proper coloring of $G$ from the sampled
colors. Besides being a combinatorial statement of its own independent
interest, this theorem was shown to have various applications to design of
algorithms for $(\Delta+1)$ coloring in different models of computation on
massive graphs such as streaming or sublinear-time algorithms.
  In this paper, we further study palette sparsification problems:
  * We prove that for $(1+\varepsilon) \Delta$ coloring, sampling only
$O_{\varepsilon}(\sqrt{\log{n}})$ colors per vertex is sufficient and necessary
to obtain a proper coloring from the sampled colors.
  * A natural family of graphs with chromatic number much smaller than
$(\Delta+1)$ are triangle-free graphs which are $O(\frac{\Delta}{\ln{\Delta}})$
colorable. We prove that sampling $O(\Delta^{\gamma} + \sqrt{\log{n}})$ colors
per vertex is sufficient and necessary to obtain a proper
$O_{\gamma}(\frac{\Delta}{\ln{\Delta}})$ coloring of triangle-free graphs.
  * We show that sampling $O_{\varepsilon}(\log{n})$ colors per vertex is
sufficient for proper coloring of any graph with high probability whenever each
vertex is sampling from a list of $(1+\varepsilon) \cdot deg(v)$ arbitrary
colors, or even only $deg(v)+1$ colors when the lists are the sets
$\{1,\ldots,deg(v)+1\}$.
  Similar to previous work, our new palette sparsification results naturally
lead to a host of new and/or improved algorithms for vertex coloring in
different models including streaming and sublinear-time algorithms.
