ISSN:
1439-6912
Keywords:
68 Q 22
;
05 C 15
;
68 R 10
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Given a connected graphG=(V, E) with |V|=n and maximum degree Δ such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with Δ colors. We generalize this as follows: letG-v be Δ-colored; then,v can be colored by considering the vertices in anO(logΔ n) radius aroundv and by recoloring anO(logΔ n) length “augmenting path” inside it. Using this, we show that Δ-coloringG is reducible inO(log3 n/logΔ) time to (Δ+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for Δ-coloring.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01200759
Permalink
