CF-Coloring of String Graphs.

Based on a joint work with Chaya Keller and Shakhar Smorodinsky.

Given a hypergraph $H=(V, E)$ a function $c : V -> N$ is said to be a CF-coloring of $H$ if for each hyperedge $e$ of $E$ there exists a vertex $v$ in $e$ s.t. $c(v) \neq c(v’)$ for $v’$ in $e \setminus {v}.$ That is, for each hyperedge some color appears exactly once. The least possible number of colors sufficient to CF-color H is called the CF-chromatic number of H. A graph G=(V,E) naturally gives rise to a hypergraph H=(V,E’) with E’={N(v) : v in V}, where N(v) stands for the neighborhood of v in G. Such an H is called open neighborhood hypergraph. By abuse, we say open CF-coloring of G instead of CF-coloring of the corresponding open neighborhood hypergraph. We call the least number of colors sufficient to open CF-color G its open CF-chromatic number. In this area, the main problem consists in finding good asymptotical bounds, in terms of the number of vertices or other graph parameters, on the CF-chromatic number of members of some class of hypergraphs. Motivated by problems of frequency assignment, the concept of CF-coloring was introduced by Even et al. in 2003 and was extensively studied since then. The research on open CF-coloring of graphs was initiated a few years later by Chelaris and Pach, who proved an upper bound of $O(\sqrt{n})$ on the open chromatic number of any graph on n vertices. On the other hand, it is not hard to come up with with graphs requiring $\Omega(\sqrt{n})$ colors in order to be open CF-colored. Open CF-coloring of graphs arising in geometric framework was also studied. One can, for example, mention the recent result of Keller and Smorodinsky that intersection graphs of Jordan regions can be open CF-colored with O(log n) colors. A string graph is the intersection graph of a family of curves, i.e., subsets of $R^2$ homeomorphic to the interval [0,1]. Motivated by the celebrated conjecture on the maximum possible number of edges in k-quasi-planar graphs on n vertices as well as practical applications to channel assignment, map labeling, and VLSI design coloring of string graphs was also studied a lot. Though both open CF-coloring of graphs and coloring of string graphs attracted the attention of numerous researchers nobody studied open CF-coloring of string graphs. After briefly introducing the area of open CF-coloring of general graphs, I will focus on open CF-coloring and its weaker variant open k-CF-coloring, where for each hyperedge some color is required to appear at least once and at most k times, of string graphs. In particular, I will talk about subclasses of the class of string graphs whose members can be efficiently open CF-colored, and some tools we use to prove such results. At the end, I will mention open problems and present a conjecture whose proof can be an important milestone in this freshly cooked area.