Abstract
We study the problem of coloring a given graph using a small number of colors in several wellestablished models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel communication (MPC) model, and the CONGESTEDCLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph G using κ(G)⋅(1+o(1)) colors, where κ(G) is the degeneracy of G: this parameter is closely related to the arboricity α(G). As a function of κ(G) alone, our results are close to best possible, since the optimal number of colors is κ(G)+1. For several classes of graphs, including realworld "big graphs," our results improve upon the number of colors used by the various (Δ(G)+1)coloring algorithms known for these models, where Δ(G) is the maximum degree in G, since Δ(G) ⩾ κ(G) and can in fact be arbitrarily larger than κ(G).
On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses at most κ(G)+O(1) colors would require Ω(n²) storage in the one pass streaming model, and Ω(n²) many queries in the general graph query model, where n is the number of vertices in the graph. These lower bounds hold even when the value of κ(G) is known in advance; at the same time, our upper bounds do not require κ(G) to be given in advance.
BibTeX  Entry
@InProceedings{bera_et_al:LIPIcs:2020:12418,
author = {Suman K. Bera and Amit Chakrabarti and Prantar Ghosh},
title = {{Graph Coloring via Degeneracy in Streaming and Other SpaceConscious Models}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {11:111:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12418},
URN = {urn:nbn:de:0030drops124182},
doi = {10.4230/LIPIcs.ICALP.2020.11},
annote = {Keywords: Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms}
}
Keywords: 

Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms 
Collection: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) 
Issue Date: 

2020 
Date of publication: 

29.06.2020 