Alladi Ramakrishnan Hall

On Coloring Problems in Congested Clique and MPC

Gopinath Mishra

NUS Singapore

Graph coloring problems are among the most extensively studied
problems in the area of distributed graph algorithms. The inherent
interaction between the local and global aspects of the coloring problems
makes them representative of a variety of problems in distributed settings.
In the distributed graph coloring problem, we are given an undirected
graph, and we want to color the nodes of it such that no edge is
monochromatic. The most fundamental graph coloring problem in distributed
computing is the (Delta+1)-coloring problem, where Delta is the maximum
degree of any node in the graph. This problem can be easily solved by a
sequential greedy algorithm, but the interaction between the local and
global aspects of graph coloring creates some non-trivial challenges in a
distributed setting. The problem has been used as a benchmark and at the
very core of the area of distributed graph algorithms. A generalization of
(Delta+1)-coloring is the (Degree+1)-list coloring (D1LC) problem which is
more challenging to solve in the distributed models. In this talk, we
discuss the results of coloring problems in distributed computing and
Massively Parallel Computation (MPC) models with a focus on some recent
developments in the (Degree+1)-list coloring (D1LC) problem in Congested
Clique and sub-linear MPC.

This is based on two joint works with Sam Coy, Artur Czumaj, and Peter
Davies.