@inproceedings{ca24a3c72eaa4c5d932576d6db1d5df7,
title = "Conflict-free colorings of shallow discs",
abstract = "We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3 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 assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.",
keywords = "Conflict-free coloring, Frequency-assignment, Wireless",
author = "Noga Alon and Shakhar Smorodinsky",
year = "2006",
doi = "10.1145/1137856.1137864",
language = "English (US)",
isbn = "1595933409",
series = "Proceedings of the Annual Symposium on Computational Geometry",
publisher = "Association for Computing Machinery (ACM)",
pages = "41--43",
booktitle = "Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06",
address = "United States",
note = "22nd Annual Symposium on Computational Geometry 2006, SCG'06 ; Conference date: 05-06-2006 Through 07-06-2006",
}