$ k $-Conflict-Free Coloring of String Graphs Academic Article uri icon


  • Abstract: Given a hypergraph $ H=(V, E) $ and an integer parameter $ k $, a coloring of $ V $ is said to be $ k $-conflict-free ($ k $-CF in short) if for every hyperedge $ S\in E $, there exists a color with multiplicity at most $ k $ in $ S $. A $ k $-CF coloring of a graph is a $ k $- CF coloring of the hypergraph induced by the (closed or punctured) neighborhoods of its vertices. The special case of $1 $-CF coloring of general graphs and hypergraphs has been studied extensively. In this paper we study $ k $-CF coloring of graphs and hypergraphs. First, we study the non-geometric case and prove that any hypergraph with $ n $ vertices and $ m $ hyperedges can be $ k $-CF colored with $\tilde {O}(m^{\frac {1}{k+ 1}}) $ colors. This bound, which extends theorems of Cheilaris and of Pach and Tardos (2009), is tight, up to a logarithmic factor.

publication date

  • January 1, 2017

published in