We deterministically compute a Δ + 1 coloring in time O(Δ_(5c+2)·(Δ_5)~(2/c)/(Δ_1)~∈ + (Δ_1)~∈ + log~* n) and O(Δ_(5c+2)·(Δ_5)~(1/c)/Δ~∈ + Δ~∈ + (Δ_5)~d log Δ_5 log n) for arbitrary constants d, ∈ and arbitrary constant integer c, where Δ_i is defined as the maximal number of nodes within distance i for a node and Δ := Δ_1. Our greedy algorithm improves the state-of-the-art Δ + 1 coloring algorithms for a large class of graphs, e.g. graphs of moderate neighborhood growth. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. If Δ ∈ Ω(log~(1+1/log~* n) n) and χ ∈ O(Δ/log~(1+1/log~* n) n) then our algorithm executes in time O(log χ + log~* n) with high probability. For graphs of polylogarithmic chromatic number the analysis reveals an exponential gap compared to the fastest Δ + 1 coloring algorithm running in time O(log Δ + {the square root of}(log n)). The algorithm works without knowledge of χ and uses less than Δ colors, i.e., (1 - 1/O(χ))Δ with high probability. To the best of our knowledge this is the first distributed algorithm for (such) general graphs taking the chromatic number χ into account.
展开▼
