Distributed Coloring of Graphs with an Optimal Number of Colors

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on coloring graphs of maximum degree Delta with at most Delta + 1 colors (or Delta colors when some simple obstructions are forbidden). When Delta is sufficiently large and c >= Delta - k(Delta) + 1, for some integer k(Delta) approximate to root Delta - 2, we give a distributed algorithm that given a c-colorable graph G of maximum degree Delta, finds a c-coloring of G in min{O((log Delta)(13/12) log n), 2(O(log Delta + root log log n))} rounds, with high probability. The lower bound Delta - k(Delta) + 1 is best possible in the sense that for infinitely many values of Delta, we prove that when chi(G) = Delta - k(Delta) deciding whether chi(G)