Locality based graph coloring

We study the problem of locality based graph coloring. This problem is motivated by the problem of assigning time slots for broadcast in mobile packet radio networks. This problem has also been studied in the context of distributed and parallel graph coloring (4, 6, 9, 8]. In this problem, one has to design a coloring algorithm that assigns a color to a vertex based on the label of the vertex and the labels on its neighbours. Linial proved an upper bound of 0(Δ²log n) and a lower bound of Δ(loglogn) on the number of colors needed to locally color an n-vertex graph with maximum vertex degree A [9, 8]. His main motivation was that repeated application of local coloring gives a fast algorithm for distributed coloring. He proved that one could get a Δ² coloring in O(log∗ n) steps this way. In this paper we improve upon the bounds for the problem of local coloring. Using a new characterization in terms of a family of set systems we design a randomized algorithm for the problem and prove an upper bound of O(Δ-2^Δloglogn). An important question left open in Linial's paper was the case of large A. The best lower bound was A + 1. Linial observed that a result of Erdos, Frankl and Fiiredi implied that his method cannot be applied to reduce the number of colors to below Δ+2/2 We obtain lower bounds that match the upper bounds within a factor that is poly-logarithmic in terms of these bounds. Of particular interest we have very precise bounds for the case when Δ > 2√n. These bounds are useful to obtain a heuristic estimate on the number of steps necessary to reduce the size of the color set from Δ² to Δ + 1, when local coloring algorithms are used iteratively. The number of steps turns out to be Θ(ΔlogΔ).