Mathematics – Combinatorics
Scientific paper
2010-05-30
Mathematics
Combinatorics
16 pages; we simplify and extend our previous results using a new potential method; new coauthor (Marek Sulovsk\'y) added
Scientific paper
Given a geometric hypergraph (or a range-space) $H=(V,\cal E)$, a coloring of its vertices is said to be conflict-free if for every hyperedge $S \in \cal E$ there is at least one vertex in $S$ whose color is distinct from the colors of all other vertices in $S$. The study of this notion is motivated by frequency assignment problems in wireless networks. We study the list-coloring (or choice) version of this notion. In this version, each vertex is associated with a set of (admissible) colors and it is allowed to be colored only with colors from its set. List coloring arises naturally in the context of wireless networks. Our main result is a list coloring algorithm based on a new potential method. The algorithm produces a stronger unique-maximum coloring, in which colors are positive integers and the maximum color in every hyperedge occurs uniquely. As a corollary, we provide asymptotically sharp bounds on the size of the lists required to assure the existence of such unique-maximum colorings for many geometric hypergraphs (e.g., discs or pseudo-discs in the plane or points with respect to discs). Moreover, we provide an algorithm, such that, given a family of lists with the appropriate sizes, computes such a coloring from these lists.
Cheilaris Panagiotis
Smorodinsky Shakhar
Sulovský Marek
No associations
LandOfFree
The potential to improve the choice: list conflict-free coloring for geometric hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The potential to improve the choice: list conflict-free coloring for geometric hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The potential to improve the choice: list conflict-free coloring for geometric hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-161913