Alon, Noga; Smorodinsky, Shakhar Conflict-free colorings of shallow discs. (English) Zbl 1184.05038 Int. J. Comput. Geom. Appl. 18, No. 6, 599-604 (2008). Summary: We prove that any collection of n discs in which each one intersects at most \(k\) others, can be colored with at most \(O(\log^3 k)\) colors so that for each point \(p\) in the union of all discs there is at least one disc in the collection containing \(p\) whose color differs from that of all other members of the collection that contain \(p\). This is motivated by a problem on frequency assignment in cellular networks, and improves the best previously known upper bound of \(O(\log n)\) when \(k\) is much smaller than \(n\). Cited in 4 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C85 Graph algorithms (graph-theoretic aspects) 52C40 Oriented matroids in discrete geometry 52B55 Computational aspects related to convexity 68W40 Analysis of algorithms 90B18 Communication networks in operations research 94A05 Communication theory Keywords:combinatorial geometry; wireless networks; conflict-free colorings Citations:Zbl 1069.68120 PDFBibTeX XMLCite \textit{N. Alon} and \textit{S. Smorodinsky}, Int. J. Comput. Geom. Appl. 18, No. 6, 599--604 (2008; Zbl 1184.05038) Full Text: DOI References: [1] DOI: 10.1002/0471722154 · doi:10.1002/0471722154 [2] DOI: 10.1007/BF02187740 · Zbl 0681.68060 · doi:10.1007/BF02187740 [3] DOI: 10.1137/S0097539702431840 · Zbl 1069.68120 · doi:10.1137/S0097539702431840 [4] DOI: 10.1137/S0097539704446682 · Zbl 1124.68077 · doi:10.1137/S0097539704446682 [5] DOI: 10.1007/s00454-005-1162-6 · Zbl 1066.05064 · doi:10.1007/s00454-005-1162-6 [6] DOI: 10.1007/BF02187683 · Zbl 0594.52004 · doi:10.1007/BF02187683 [7] Pach J., Discrete and Computational Geometry, The Goodman-Pollack Festschrift (2003) · Zbl 1014.00040 [8] DOI: 10.1137/050642368 · Zbl 1141.05064 · doi:10.1137/050642368 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.