Near-optimal distributed degree+1 coloring

Summary

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)-list-coloring (D1LC) problem, where each node v of degree dv is assigned a palette of dv+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(log3logn)-round algorithm due to Chang, Li, and Pettie, no o(logn)-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, our algorithm runs in O(log3 logn) time, matching the best bound known for (Δ+1)-coloring. A key contribution is a subroutine to generate slack for D1LC, which almost immediately leads to a palette sparsification theorem for D1LC when placed into the framework of works by Assadi, Chen, and Khanna and Alon and Assadi. 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 semi-streaming algorithm in dynamic streams; and an Õ(n√n)-time query algorithm.