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. Next, we study {\em string graphs}. We consider several families of string graphs on $n$ vertices for which the $1$-CF chromatic number w.r.t. punctured neighborhoods is $\Omega(\sqrt{n}) 查看全文>>