Abstract
A valid edgecoloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. (Note that the maximum degree, Delta, is a trivial lower bound.) In this paper, we revisit this fundamental problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model:
 Massively Parallel Computation: We give a randomized MPC algorithm that with high probability returns a Delta+O~(Delta^(3/4)) edge coloring in O(1) rounds using O(n) space per machine and O(m) total space. The space per machine can also be further improved to n^(1Omega(1)) if Delta = n^Omega(1). Our algorithm improves upon a previous result of Harvey et al. [SPAA 2018].
 Graph Streaming: Since the output of edgecoloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors.
We give a onepass O~(n)space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another onepass O~(n)space algorithm that requires O(Delta^2) colors.
BibTeX  Entry
@InProceedings{behnezhad_et_al:LIPIcs:2019:11136,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Marina Knittel and Hamed Saleh},
title = {{Streaming and Massively Parallel Algorithms for Edge Coloring}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {15:115:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11136},
URN = {urn:nbn:de:0030drops111361},
doi = {10.4230/LIPIcs.ESA.2019.15},
annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring}
}
Keywords: 

Massively Parallel Computation, Streaming, Edge Coloring 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 