abstract
vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. in this paper we present a new algorithm for (∆ + 1)-list coloring in the randomized
local model running in o(log ∗ n + detd (poly log n)) time, where detd (n′ ) is the deterministic complexity of (deg +1)-list coloring (v’s palette has size deg(v) + 1) on n′ -vertex graphs.
this improves √upon a previous randomized algorithm of harris, schneider, and su [18] with
complexity o( log ∆ + log log n + detd (poly log n)), and is dramatically faster than the best
known
√ deterministic algorithm of fraigniaud, heinrich, and kosowski [14], with complexity
o( ∆ log2.5 ∆ + log∗ n).
our algorithm appears to be optimal. it matches the ω(log∗ n) randomized lower bound,
due to naor [25] and sort of matches the ω(det(poly log n)) randomized lower bound due to
chang, kopelowitz, and pettie [7], where det is the deterministic complexity
of (∆ + 1)-list
√
′
coloring. the best known upper bounds on detd (n′ ) and det(n′ ) are both 2o( log n ) (panconesi
and srinivasan [26]) and it is quite plausible that the complexities of both problems are the
same, asymptotically.