H. T. Nguyen

Communication-Efficient $(1+\varepsilon)\Delta$-Edge Coloring and Lov\'asz Local Lemma

We study edge coloring in the two-party edge-partition model, where Alice and Bob each know part of the edge set and must jointly produce a proper coloring with little communication. Previous work gave a deterministic $(2\Delta-1)$-edge-coloring protocol using $O(n)$ bits, leaving open whether fewer colors can be obtai...