@article {17666,
	title = {The local nature of Δ-coloring and its algorithmic applications},
	journal = {Combinatorica},
	volume = {15},
	year = {1995},
	month = {1995///},
	pages = {255 - 280},
	abstract = {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{\textquoteright} 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 {\textquotedblleft}augmenting path{\textquotedblright} 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.},
	isbn = {0209-9683},
	url = {http://dx.doi.org/10.1007/BF01200759},
	author = {Panconesi,Alessandro and Srinivasan, Aravind}
}
