Efficient Deterministic Distributed Coloring with Small Bandwidth
share
We show that the (degree+1)-list coloring problem can be solved deterministically in O(D ·log n ·log^3 Δ) in the CONGEST model, where D is the diameter of the graph, n the number of nodes, and Δ is the maximum degree. Using the network decomposition algorithm from Rozhon and Ghaffari this implies the first efficient deterministic, that is, polylog n-time, CONGEST algorithm for the Δ+1-coloring and the (degree+1)-list coloring problem. Previously the best known algorithm required 2^O(√(log n)) rounds and was not based on network decompositions. Our results also imply deterministic O(log^3 Δ)-round algorithms in MPC and the CONGESTED CLIQUE.
READ FULL TEXT
