Fast Distributed -Edge Coloring in Bipartite Graphs
In the authors' words
We show that, on bipartite -vertex graphs in the LOCAL model of distributed computation, -edge coloring can be solved deterministically in rounds for some function . In particular this implies a deterministic -round upper bound for -edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose -dependencies are rounds deterministically and rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of -edge coloring that corresponds to a local-palette strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge has to be colored with a color from . For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.