Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors

DOI10.1007/s00454-012-9425-5zbMath1246.68167OpenAlexW1984121377MaRDI QIDQ443903

Sathish Govindarajan, Deepak Ajwani, Saurabh Ray, Khaled M. Elbassioni

Publication date: 13 August 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9425-5

zbMATH Keywords

monotone sequencesconflict-free coloringaxis-parallel rectanglesboundary setsfrequency assignment in wireless networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (15)

Dynamic conflict-free colorings in the plane ⋮ Coloring Axis-Parallel Rectangles ⋮ Conflict-Free Coloring of Graphs ⋮ Structural parameterization for minimum conflict-free colouring ⋮ Coloring points with respect to squares ⋮ Coloring lines and Delaunay graphs with respect to boxes ⋮ Coloring half-planes and bottomless rectangles ⋮ On variants of conflict-free-coloring for hypergraphs ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Coloring axis-parallel rectangles ⋮ Dynamic Offline Conflict-Free Coloring for Unit Disks ⋮ Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ Unnamed Item ⋮ Dynamic Conflict-Free Colorings in the Plane

Cites Work

• Coloring graphs with sparse neighborhoods
• Conflict-free coloring of points and simple regions in the plane
• On the chromatic number of some geometric hypergraphs
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
• Conflict-Free Coloring and its Applications
• Conflict-Free Colorings of Rectangles Ranges
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors