Prof. Michael Elkin

Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2δ - l)-edge-coloring can be computed in time smaller than log^∈ n for any ∈ > 0, specifically, in e^o(√log log n) rounds. This establishes a separation between the (2δ- l)-edge-coloring and Maximal Matching problems, as the latter is known to require ω(√log n) time [15]. No such separation is currently known between the (δ + l)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ∈)A-edge-coloring algorithm for an arbitrarily small constant ∈ > 0. This result applies whenever A > Ae, for some constant Ae which depends on e. The running time of this algorithm is O(log∗ δ +log n/δ^1-0(1)). A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed δ ≥ (log n)^1+ω(1). For A = (log n) ¹⁺ⁿ⁽¹⁾ the running time of our algorithm is only O(log∗ n). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2δ - l)-edge-coloring also follows from our more general results concerning (1 - ∈)-locally sparse graphs. Specifically, we devise a (δ + l)-vertex coloring algorithm for (1 - ∈)-locally sparse graphs that runs in O(log∗ δ + log(l/e)) rounds for any ∈ > 0, provided that ∈δ = (log n)^1+ω(1). We conclude that the (δ + 1)-vertex coloring problem for (1 - ∈)-locally sparse graphs can be solved in O(log(l/∈)) + e^{o√loglog n} time. This imply our result about (2δ - l)-edge-coloring, because (2δ - 1)-edge-coloring reduces to (δ + 1)-vertex-coloring of the line graph of the original graph, and because line graphs are (1/2 + o(1))-locally sparse.