# $k$-Conflict-Free Coloring of String Graphs Academic Article

•
• Overview
•

### abstract

• 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