×

Conflict-free colorings of shallow discs. (English) Zbl 1184.05038

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\).

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

Citations:

Zbl 1069.68120
PDFBibTeX XMLCite
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.