Shakhar Smorodinsky

In this paper, we study coloring problems related to frequency assignment problems in cellular networks. In abstract setting, the problems are of the following two types: CF-coloring of regions: Given a finite family S of n regions of some fixed type (such as discs, pseudo-discs, axis-parallel rectangles, etc.), what is the minimum integer k, such that one can assign a color to each region of S, using a total of at most k colors, such that the resulting coloring has the following property: For each point p ∈ ∪_b∈Sb there is at least one region b ∈ S that contains p in its interior, whose color is unique among all regions in S that contain p in their interior (in this case we say that p is being 'served' by that color). We refer to such a coloring as a conflict-free coloring of S (CF-coloring in short). CF-coloring of a range space: Given a set P of n points in ℝ^d and a set R of ranges (for example, the set of all discs in the plane), what is the minimum integer k, such that one can color the points of P by k colors, so that for any r ∈ R, with P ∩ r ≠ θ, there is at least one point q ∈ P ∩ r that is assigned a unique color among all colors assigned to points of P ∩ r (in this case we say that r is 'served' by that color). We refer to such a coloring as a conflict-free coloring of (P, R) (CF-coloring in short).