Conflict-Free Coloring of Intersection Graphs of Geometric Objects
- PDF / 515,513 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 221 Views
Conflict-Free Coloring of Intersection Graphs of Geometric Objects Chaya Keller1 · Shakhar Smorodinsky1 Received: 15 January 2018 / Revised: 9 March 2019 / Accepted: 19 April 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract In 2002, Even et al. introduced and studied the notion of conflict-free colorings of geometrically defined hypergraphs. They motivated it by frequency assignment problems in cellular networks. This notion has been extensively studied since then. A conflictfree coloring of a graph is a coloring of its vertices such that the neighborhood (pointed or closed) of each vertex contains a vertex whose color differs from the colors of all other vertices in that neighborhood. In this paper we study conflict-free colorings of intersection graphs of geometric objects. We show that any intersection graph of n pseudo-discs in the plane admits a conflict-free coloring with O(log n) colors, with respect to both closed and pointed neighborhoods. We also show that the latter bound is asymptotically sharp. Using our methods, we obtain the following strengthening of the two main results of Even et al.: Any family F of n discs in the plane can be colored with O(log n) colors in such a way that for any disc B in the plane, not necessarily from F, the set of discs in F that intersect B contains a uniquely-colored element. In view of the original motivation to study such colorings, this strengthening suggests further applications to frequency assignment in wireless networks. Finally, we present bounds on the number of colors needed for conflict-free colorings of other classes of
A preliminary version of this paper was presented at the SODA’2018 conference. Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach C. Keller: Research partially supported by Grant 635/16 from the Israel Science Foundation, the Shulamit Aloni Post-Doctoral Fellowship of the Israeli Ministry of Science and Technology, and by the Kreitman Foundation Post-Doctoral Fellowship. S. Smorodinsky: Research partially supported by Grant 635/16 from the Israel Science Foundation. Chaya Keller [email protected] Shakhar Smorodinsky [email protected] 1
Department of Mathematics, Ben-Gurion University of the NEGEV, Be’er Sheva, Israel
123
Discrete & Computational Geometry
intersection graphs, including intersection graphs of axis-parallel rectangles and of ρ-fat objects in the plane. Keywords Conflict-free coloring · Geometric graphs · Pseudo-discs · Axis-parallel rectangles · List coloring Mathematics Subject Classification 05C15 · 05C10
1 Introduction 1.1 Background A conflict-free coloring (CF-coloring in short) of a hypergraph H is a coloring of its vertices in which each hyperedge contains a uniquely colored vertex (i.e., a vertex whose color differs from the colors of all other vertices that belong to the hyperedge). Conflict-free colorings of hypergraphs were introduced in FOCS’2002 by Even et al. [10], in the context of the following problem of frequency assignment in cellular networ
Data Loading...
