Vi bevisar att varje samling av n skivor där var och en skär på de flesta k andra, kan färgas med högst O(log 3 k) färger så att för varje punkt p i föreningen av alla skivor det finns minst en skiva i samlingen som innehåller p vars färg skiljer sig från den för alla andra medlemmar i samlingen som innehåller p. Detta motiveras av ett problem på frekvenstilldelningar i cellulära nätverk, och förbättrar den mest kända övre gränsen av O (log n) när k är mycket mindre än n.
Alon och Smorodinsky REF utökar detta genom att visa att varje familj av diskar, där varje disk skär som mest k andra, kan färgas med O(log 3 k) färger.
Conflict-free colorings of shallow discs
{'venue': "SCG '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}