## Abstract

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(Δ^{2}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 Δ^{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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993 |

Publisher | Association for Computing Machinery |

Pages | 201-207 |

Number of pages | 7 |

ISBN (Electronic) | 0897915917 |

DOIs | |

State | Published - Jun 1 1993 |

Externally published | Yes |

Event | 25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States Duration: May 16 1993 → May 18 1993 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F129585 |

ISSN (Print) | 0737-8017 |

### Other

Other | 25th Annual ACM Symposium on Theory of Computing, STOC 1993 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 5/16/93 → 5/18/93 |

## All Science Journal Classification (ASJC) codes

- Software