The potential to improve the choice, list conflict-free coloring for geometric hypergraphs

DOI10.1145/1998196.1998266zbMATH Open1283.05191arXiv1005.5520OpenAlexW1972678475MaRDI QIDQ5404457FDOQ5404457

Authors: Panagiotis Cheilaris, Marek Sulovský, Shakhar Smorodinsky 

Publication date: 24 March 2014

Published in: Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: Given a geometric hypergraph (or a range-space) $H=(V,calE)$, a coloring of its vertices is said to be conflict-free if for every hyperedge $SincalE$ 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.

Full work available at URL: https://arxiv.org/abs/1005.5520

Recommendations

• Conflict-free colourings of graphs and hypergraphs
• On conflict-free multi-coloring
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks

zbMATH Keywords

geometryhypergraphvertex coloringconflict-freeunique-maximum

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited In (2)

• Conflict-free coloring of graphs
• Conflict-free coloring of intersection graphs

This page was built for publication: The potential to improve the choice, list conflict-free coloring for geometric hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404457)