View PDF

Abstract:We explore the complexity of edge coloring in the LOCAL model in different palette size regimes.
1. Lower Bounds: First, we simplify the round elimination technique of Brandt et al. and prove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$ time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees. Second, we show that a natural approach to computing $(\Delta+1)$-edge colorings (Vizing's theorem) via extending partial colorings by iteratively re-coloring parts of the graph in the worst case requires recoloring subgraphs of diameter $\Omega(\Delta\log n)$.
2. Upper Bounds on General Graphs: We give a randomized edge coloring algorithm that can use palette sizes as small as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier for randomized approaches. Our algorithm employs a permissive version of the constructive Lovasz local lemma as a black box. The runtime of algorithm varies for different choices of $\Delta$ and palette size. For example, our algorithm computes a $(1+\epsilon)\Delta$-edge coloring in $O(\log n)$ time when $\epsilon \geq (\log^3 \Delta) / \sqrt{\Delta}$, or $O(\log_{\Delta} n) + (\log \log n)^{3 + o(1)}$ time when $\epsilon = \Omega(1)$.
3. Upper Bounds on Trees: We show that the $\Omega(\log_\Delta \log n)$ lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovasz local lemma algorithm for tree-structured dependency graphs. Specifically, our $(1+\epsilon)\Delta$-edge coloring algorithm for trees takes $O(\log(1 / \epsilon)) \cdot \max\{\frac{\log\log n}{\log\log\log n},\, \log_{\log \Delta} \log n\}$ time when $\epsilon \geq (\log^3 \Delta) / \sqrt{\Delta}$, or $O\left( \max\{\frac{\log\log n}{\log\log\log n},\, \log_{\Delta} \log n\}\right)$ time when $\epsilon = \Omega(1)$.

Submission history

From: Yi-Jun Chang [view email]
[v1] Mon, 14 Aug 2017 19:47:53 UTC (57 KB)
[v2] Thu, 19 Apr 2018 03:34:02 UTC (78 KB)
[v3] Wed, 5 Aug 2026 03:30:53 UTC (203 KB)