The local nature of Δ-coloring and its algorithmic applications

Given a connected graph G =( V, E ) with | V ⊧ n and maximum degree Δ such that G is neither a complete graph nor an odd cycle, Brooks' theorem states that G can be colored with Δ colors. We generalize this as follows: let G - v be Δ-colored; then, v can be colored by considering the vertices in an O (log Δ n ) radius around v and by recoloring an O (log Δ n ) length “augmenting path” inside it. Using this, we show that Δ-coloring G is reducible in O (log 3 n /logΔ) time to (Δ+1)-vertex coloring G in a distributed model of computation. This leads to fast distributed algorithms and a linear-processor NC algorithm for Δ-coloring.