Given a set of unit-disks in the plane with union area @math , what fraction of @math can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1 4 and proved @math . Motivated by the problem of channel-assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least @math of the union area and prove @math . We also provide an @math algorithm to select a subset achieving a @math bound.
Motivated by a frequency assignment problem in cellular networks, we introduce and study a new coloring problem that we call minimum conflict-free coloring (min-CF-coloring). In its general form, the input of the min-CF-coloring problem is a set system @math , where each @math is a subset of X. The output is a coloring @math of the sets in @math that satisfies the following constraint: for every @math there exists a color @math and a unique set @math such that @math and @math . The goal is to minimize the number of colors used by the coloring @math . Min-CF-coloring of general set systems is not easier than the classic graph coloring problem. However, in view of our motivation, we consider set systems induced by simple geometric regions in the plane. In particular, we study disks (both congruent and noncongruent), axis-parallel rectangles (with a constant ratio between the smallest and largest rectangle), regular hexagons (with a constant ratio between the smallest and largest hexagon), and general congruent centrally symmetric convex regions in the plane. In all cases we have coloring algorithms that use O(log n) colors (where n is the number of regions). Tightness is demonstrated by showing that even in the case of unit disks, @math colors may be necessary. For rectangles and hexagons we also obtain a constant-ratio approximation algorithm when the ratio between the largest and smallest rectangle (hexagon) is a constant. We also consider a dual problem of CF-coloring points with respect to sets. Given a set system @math , the goal in the dual problem is to color the elements in X with a minimum number of colors so that every set @math contains a point whose color appears only once in S. We show that O(log |X|) colors suffice for set systems in which X is a set of points in the plane and the sets are intersections of X with scaled translations of a convex region. This result is used in proving that O(log n) colors suffice in the primal version. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open.  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∈S b 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 Rd 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∈≠O, 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).