Sublinear Algorithms for $(\Delta +1)$ Vertex Coloring

Sepehr Assadi, Yu Chen, Sanjeev Khanna

Any graph with maximum degree $\Delta$ admits a proper vertex coloring with $\Delta +1$ colors that can be found via a simple sequential greedy algorithm in linear time and space. But can on…