The potential to improve the choice: list conflict-free coloring for geometric hypergraphs Conference Paper uri icon


  • Given a geometric hypergraph (or a range-space) H=(V, E), a coloring of its vertices is said to be conflict-free if for every hyperedge S∈ 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 …

publication date

  • January 1, 2011