Deterministic distributed vertex coloring in polylogarithmic time Academic Article uri icon


  • Consider an n-vertex graph G=(V, E) of maximum degree Δ, and suppose that each vertex v∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ+ 1, or slightly more than Δ+ 1, colors using as few rounds of communication as possible.(The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years [Alon et al. 1986; Luby 1986]. Specifically, these algorithms produce a (Δ+ 1)-coloring within O (log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O (Δ 2) colors. This algorithm was devised in a seminal …

publication date

  • January 1, 2011