The Complexity of Distributed Edge Coloring with Small Palettes

Authors:
Publisher website
Google Scholar
Abstract
The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.