  We present a new approach to randomized distributed graph coloring that is
simpler and more efficient than previous ones. In particular, it allows us to
tackle the $(\operatorname{deg}+1)$-list-coloring (D1LC) problem, where each
node $v$ of degree $d_v$ is assigned a palette of $d_v+1$ colors, and the
objective is to find a proper coloring using these palettes. While for
$(\Delta+1)$-coloring (where $\Delta$ is the maximum degree), there is a fast
randomized distributed $O(\log^3\log n)$-round algorithm (Chang, Li, and Pettie
[SIAM J. Comp. 2020]), no $o(\log n)$-round algorithms are known for the D1LC
problem.
  We give a randomized distributed algorithm for D1LC that is optimal under
plausible assumptions about the deterministic complexity of the problem. Using
the recent deterministic algorithm of Ghaffari and Kuhn [FOCS2021], our
algorithm runs in $O(\log^3 \log n)$ time, matching the best bound known for
$(\Delta+1)$-coloring. In addition, it colors all nodes of degree
$\Omega(\log^7 n)$ in $O(\log^* n)$ rounds.
  A key contribution is a subroutine to generate slack for D1LC. When placed
into the framework of Assadi, Chen, and Khanna [SODA2019] and Alon and Assadi
[APPROX/RANDOM2020], this almost immediately leads to a palette sparsification
theorem for D1LC, generalizing previous results. That gives fast algorithms for
D1LC in three different models: an $O(1)$-round algorithm in the MPC model with
$\tilde{O}(n)$ memory per machine; a single-pass semi-streaming algorithm in
dynamic streams; and an $\tilde{O}(n\sqrt{n})$-time algorithm in the standard
query model.
