# Conflict-Free coloring of String Graphs

### Wednesday, May 29th, 2019, 16:10

### Schreiber 309

### Conflict-Free coloring of String Graphs

### Shakhar Smorodinsky, BGU

### Abstract:

Given a graph $G=(V,E)$ and a fixed integer $k >1$, a coloring of the vertices of $G$ is called k-Conflict-Free (kCF in short) if for any vertex $v$ there exists at least one color that is assigned to at least one and at most $k$ of its neighbors. (there are two versions of the notion of neighborhood: open where it is the set $N(v)$ of all neighbors of $v$ or closed which is ${v} \cup N(v)$.

For $k=1$ such colorings have been studied extensively. In particular by J. Pach, G. Tardos, by P. Cheilaris, by Z. Abel, V. Alvarez, E.. Demaine, S. Fekete, A. Gour, A. Hesterberg, P. Keldenich, C. Scheffer and by R. Glebov, T. Sz\'{a}bo and G. Tardos for general graphs.
In this talk we focus on string graphs. That is, intersection graphs of simple Jordan curves in the plane.

Joint work with Chaya Keller and Alexandre Rok