Sharp Bounds on Formation-free Sequences
Seth Pettie · 2015
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Δ − 1)-edge-coloring can be computed in time smaller than log ε n for any ε > 0, specifically, in e O ([EQUATION]log log n ) rounds. This establishes a separation between the (2Δ − 1)-edge-coloring and Maximal Matching problems, as the latter is known to require Ω([EQUATION]log n ) time [15]. No such separation is currently known between the (Δ + 1)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ε)Δ-edge-coloring algorithm for an arbitrarily small constant ε > 0. This result applies whenever Δ ≥ Δ ε , for some constant Δ ε which depends on ε. The running time of this algorithm is O (log* Δ + [EQUATION]). A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n ) 1+Ω(1) . For Δ = (log n ) 1+Ω(1) 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Δ − 1)-edge-coloring also follows from our more general results concerning (1 − ε)- locally sparse graphs. Specifically, we devise a (Δ + 1)-vertex coloring algorithm for (1 − ε)-locally sparse graphs that runs in O (log* Δ + log(1/ε)) 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(1/ε)) + e O ([EQUATION]log log n ) time. This imply our result about (2Δ − 1)-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.