Abstract
(Delta+1)vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where in each round, every pair of vertices can exchange O(log n) bits of information.
In a recent breakthrough, YiJun Chang, Wenzheng Li, and Seth Pettie [CLPSTOC'18] presented a randomized (Delta+1)list coloring algorithm in the LOCAL model that works in O(log^*n+Det_{deg}(log log n)) rounds, where Det_{deg}(n') is the deterministic LOCAL complexity of (deg+1)list coloring algorithm on n'vertex graphs. Unfortunately, the CLP algorithm uses large messages and hence cannot be efficiently implemented in the congested clique model when the maximum degree Delta is large (in particular, when Delta=omega(sqrt{n})).
Merav Parter [PICALP'18] recently provided a randomized (Delta+1)coloring algorithm in O(log log Delta * log^* Delta) congested clique rounds based on a careful partitioning of the input graph into almostindependent subgraphs with maximum degree sqrt{n}. In this work, we significantly improve upon this result and present a randomized (Delta+1)coloring algorithm with O(log^* Delta) rounds, with high probability. At the heart of our algorithm is an adaptation of the CLP algorithm for coloring a subgraph with o(n) vertices and maximum degree Omega(n^{5/8}) in O(log^* Delta) rounds. The approach is built upon a combination of techniques, this includes: the graph sparsification of [ParterICALP'18], and a palette sampling technique adopted to the CLP framework.
BibTeX  Entry
@InProceedings{parter_et_al:LIPIcs:2018:9828,
author = {Merav Parter and HsinHao Su},
title = {{Randomized (Delta+1)Coloring in O(log* Delta) Congested Clique Rounds}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {39:139:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9828},
URN = {urn:nbn:de:0030drops98286},
doi = {10.4230/LIPIcs.DISC.2018.39},
annote = {Keywords: Distributed Graph Algorithms, Coloring, congested clique}
}
Keywords: 

Distributed Graph Algorithms, Coloring, congested clique 
Collection: 

32nd International Symposium on Distributed Computing (DISC 2018) 
Issue Date: 

2018 
Date of publication: 

04.10.2018 