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

DOI10.1007/S00454-012-9425-5MaRDI QIDQ443903zbMATH OpenOpenAlexFDO

Authors Deepak Ajwani, Sathish Govindarajan, Saurabh Ray, Khaled 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

axis-parallel rectanglesboundary setsconflict-free coloringfrequency assignment in wireless networksmonotone sequences

Mathematics Subject Classification ID

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

Recommendations

• Conflict-Free Colorings of Rectangles Ranges
• On conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• scientific article; zbMATH DE number 2209737

Cites work

• Coloring graphs with sparse neighborhoods
• Conflict-free coloring and its applications
• Conflict-free coloring of points and simple regions in the plane
• Conflict-Free Colorings of Rectangles Ranges
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• scientific article; zbMATH DE number 5506190 (Why is no real title available?)
• scientific article; zbMATH DE number 5506191 (Why is no real title available?)
• scientific article; zbMATH DE number 2209737 (Why is no real title available?)
• On the chromatic number of some geometric hypergraphs
• Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
• Online conflict-free coloring for intervals
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds

Cited in

(21)

• Dynamic conflict-free colorings in the plane
• Coloring points with respect to squares
• Structural parameterization for minimum conflict-free colouring
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
• Dynamic Offline Conflict-Free Coloring for Unit Disks
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Coloring half-planes and bottomless rectangles
• Conflict-free coloring of graphs
• Parameterized Complexity of Conflict-Free Graph Coloring
• On variants of conflict-free-coloring for hypergraphs
• Dynamic conflict-free colorings in the plane
• Conflict-free coloring of intersection graphs
• Coloring Axis-Parallel Rectangles
• Conflict-Free Colorings of Rectangles Ranges
• scientific article; zbMATH DE number 2209737 (Why is no real title available?)
• Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs
• Coloring lines and Delaunay graphs with respect to boxes
• Conflict-free colouring of subsets
• Coloring axis-parallel rectangles

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443903)