Personal tools
You are here: Home CG seminar 2019 Conflict-Free coloring of String Graphs
« October 2019 »
October
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Conflict-Free coloring of String Graphs

Wednesday, May 29th, 2019, 16:10

Schreiber 309

underline

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

  

Document Actions