## ICS 269, Spring 2006: Theory Seminar

### May 19, 2006, in CS 243

# Conflict-Free Coloring of Shallow Discs

## Authored by: N. Alon and S. Smorodinsky

#### (to appear in Symp. on Computational Geometry, SoCG'06)

## Presented by Jeremy Yu Meng

Abstract:

We prove that any collection of n discs in which each one intersects at
most *k* others, can be colored with at most *O*(log^{3}*k*) colors so that for
each point *p* in the union of all discs there is at least one disc in the
collection containing *p* whose color differs from that of all other members
of the collection that contain *p*. This is motivated by a problem on
frequency assignments in cellular networks, and improves the best
previously known upper bound of *O*(log *n*) when *k* is much smaller than *n*.