Conflict-free coloring made stronger

DOI10.1007/978-3-642-13731-0_11zbMATH1284.05100OpenAlexW3124376956MaRDI QIDQ3569883FDOQ3569883

Authors Elad Aigner-Horev, Roi Krakovski, Shakhar Smorodinsky

Publication date 22 June 2010

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

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

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)

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.

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

Cited in

(20)

• Conflict-free coloring of intersection graphs
• Conflict-free colouring of subsets
• Strong conflict-free coloring for intervals
• Strong conflict-free coloring for intervals
• Dynamic conflict-free colorings in the plane
• On The Chromatic Number of Geometric Hypergraphs
• Coloring planar homothets and three-dimensional hypergraphs
• Conflict-free coloring of string graphs
• Conflict-free coloring of intersection graphs
• Conflict-free coloring of points and simple regions in the plane
• Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
• Conflict free colorings of (strongly) almost disjoint set-systems
• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• On variants of conflict-free-coloring for hypergraphs
• scientific article; zbMATH DE number 2209737 (Why is no real title available?)
• Exactly hittable interval graphs
• A short note on open-neighborhood conflict-free colorings of graphs
• Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points
• Dynamic conflict-free colorings in the plane
• Conflict-free coloring of graphs

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)