Abstract
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 >= Deltak_Delta+1, for some integer k_Delta ~~ sqrt{Delta}2, we give a distributed algorithm that given a ccolorable graph G of maximum degree Delta, finds a ccoloring of G in min{O((log Delta)^{13/12}log n), 2^{O(log Delta+sqrt{log log n})}} rounds, with high probability. The lower bound Deltak_Delta+1 is best possible in the sense that for infinitely many values of Delta, we prove that when chi(G) <= Deltak_Delta, finding an optimal coloring of G requires Omega(n) rounds. Our proof is a light adaptation of a remarkable result of Molloy and Reed, who proved that for Delta large enough, for any c >= Deltak_Delta deciding whether chi(G) <= c is in P, while EmbdenWeinert et al. proved that for c <= Deltak_Delta1, the same problem is NPcomplete. Note that the sequential and distributed thresholds differ by one.
Our first result covers the case where the chromatic number of the graph ranges between Deltasqrt{Delta} and Delta+1. Our second result covers a larger range, but gives a weaker bound on the number of colors: For any sufficiently large Delta, and Omega(log Delta) <= k <= Delta/100, we prove that every graph of maximum degree Delta and clique number at most Deltak can be efficiently colored with at most Deltaepsilon k colors, for some absolute constant epsilon >0, with a randomized algorithm running in O(log n/log log n) rounds with high probability.
BibTeX  Entry
@InProceedings{bamas_et_al:LIPIcs:2019:10249,
author = {{\'E}tienne Bamas and Louis Esperet},
title = {{Distributed Coloring of Graphs with an Optimal Number of Colors}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {10:110:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10249},
doi = {10.4230/LIPIcs.STACS.2019.10},
annote = {Keywords: Graph coloring, distributed algorithm, maximum degree}
}
Keywords: 

Graph coloring, distributed algorithm, maximum degree 
Collection: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 
Issue Date: 

2019 
Date of publication: 

12.03.2019 