Locality based graph coloring

Mario Szegecly, Sundar Visbwanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

61 Scopus citations


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(Δ2log 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 Δ2 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 Δ2 to Δ + 1, when local coloring algorithms are used iteratively. The number of steps turns out to be Θ(ΔlogΔ).

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Number of pages7
ISBN (Electronic)0897915917
StatePublished - Jun 1 1993
Externally publishedYes
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017


Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
Country/TerritoryUnited States
CitySan Diego

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Locality based graph coloring'. Together they form a unique fingerprint.

Cite this