Near-optimal distributed degree+1 coloring

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 (deg +1)-listcoloring (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 (∆ + 1)-coloring (where ∆ is the maximum degree), there is a fast randomized distributed O(log 3 log n)-round algorithm (Chang, Li, and Pettie [CLP20]), 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 [GK21], our algorithm runs in O(log 3 log n) time, matching the best bound known for (∆ + 1)-coloring. In addition, it colors all nodes of degree Ω(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 [ACK19] and Alon and Assadi [AA20], this almost immediately leads to a palette sparsification theorem for D1LC, generalizing the results of [ACK19, AA20]. That gives fast algorithms for D1LC in three different models: an O(1)round algorithm in the MPC model with Õ(n) memory per machine; a single-pass semistreaming algorithm in dynamic streams; and an Õ(n √ n)-time algorithm in the standard query model. * This paper incorporates results from the technical report [HNT21] (by a subset of the authors of this paper) on (∆+1)-coloring in the Local model and is to be considered as the publication of that work. This excludes the additional results in [HNT21] needed for a Congest implementation, which will be published separately later.