Brief Announcement: Towards Optimal Distributed Delta Coloring

The Δ-vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS'16]. Despite recent progress in the design of efficient Δ-coloring algorithms, there is currently a polynomial gap between the upper and lower bounds.