Distributed (\Delta+1)-Coloring in Sublogarithmic Rounds

back to overview


Harris, D. G., Schneider, J., & Su, H.-H. (2016). Distributed (\Delta 1)-Coloring in Sublogarithmic Rounds. Paper presented at the Symposium on the Theory of Computing (STOC).

Publication type

Paper in Conference Proceedings


The (Delta + 1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (Delta+1)-coloring running in O(sqrt(log Delta))+ 2^O(sqrt( log log n)) rounds with probability 1-1/n in a graph with n nodes and maximum degree Delta. This implies that the (Delta + 1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains Delta + 1 colors.


Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management

Original Source URL