Conflict-free coloring made stronger

DOI10.1007/978-3-642-13731-0_11zbMATH Open1284.05100arXiv1006.2926OpenAlexW3124376956MaRDI QIDQ3569883FDOQ3569883

Roi Krakovski, Elad Aigner-Horev, Shakhar Smorodinsky

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In FOCS 2002, Even et al. showed that any set of $n$ discs in the plane can be Conflict-Free colored with a total of at most $O(logn)$ colors. That is, it can be colored with $O(logn)$ colors such that for any (covered) point $p$ there is some disc whose color is distinct from all other colors of discs containing $p$. They also showed that this bound is asymptotically tight. In this paper we prove the following stronger results: �egin{enumerate} item [(i)] Any set of $n$ discs in the plane can be colored with a total of at most $O(klogn)$ colors such that (a) for any point $p$ that is covered by at least $k$ discs, there are at least $k$ distinct discs each of which is colored by a color distinct from all other discs containing $p$ and (b) for any point $p$ covered by at most $k$ discs, all discs covering $p$ are colored distinctively. We call such a coloring a {em $k$-Strong Conflict-Free} coloring. We extend this result to pseudo-discs and arbitrary regions with linear union-complexity. item [(ii)] More generally, for families of $n$ simple closed Jordan regions with union-complexity bounded by $O(n^{1+alpha})$, we prove that there exists a $k$-Strong Conflict-Free coloring with at most $O(k{n}^{a}lpha)$ colors. item [(iii)] We prove that any set of $n$ axis-parallel rectangles can be $k$-Strong Conflict-Free colored with at most $O(klo{g}^{2}n)$ colors. item [(iv)] We provide a general framework for $k$-Strong Conflict-Free coloring arbitrary hypergraphs. This framework relates the notion of $k$-Strong Conflict-Free coloring and the recently studied notion of $k$-colorful coloring. end{enumerate} All of our proofs are constructive. That is, there exist polynomial time algorithms for computing such colorings.

Full work available at URL: https://arxiv.org/abs/1006.2926

Recommendations

• Conflict-free coloring of points and simple regions in the plane
• On The Chromatic Number of Geometric Hypergraphs
• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• scientific article; zbMATH DE number 2209737
• Strong conflict-free coloring for intervals

zbMATH Keywords

discrete geometrywireless networksgeometric hypergraphsconflict-free colorings

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited In (18)

• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• Conflict-Free Coloring of Intersection Graphs
• Dynamic conflict-free colorings in the plane
• Conflict-free coloring of points and simple regions in the plane
• Title not available (Why is that?)
• Exactly hittable interval graphs
• Conflict-free coloring of string graphs
• Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points.
• Title not available (Why is that?)
• Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
• Dynamic Conflict-Free Colorings in the Plane
• Strong conflict-free coloring for intervals
• On The Chromatic Number of Geometric Hypergraphs
• Conflict-free colouring of subsets
• Conflict-Free Coloring of Graphs
• A Short Note on Open-Neighborhood Conflict-Free Colorings of Graphs
• On variants of conflict-free-coloring for hypergraphs
• Coloring planar homothets and three-dimensional hypergraphs

This page was built for publication: Conflict-free coloring made stronger

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