
Louis Esperet

Daniel Gonçalves

Arnaud Labourel
Keywords:
Graph coloring, String graphs
Abstract
For a family of geometric objects in the plane $\mathcal{F}=\{S_1,\ldots,S_n\}$, define $\chi(\mathcal{F})$ as the least integer $\ell$ such that the elements of $\mathcal{F}$ can be colored with $\ell$ colors, in such a way that any two intersecting objects have distinct colors. When $\mathcal{F}$ is a set of pseudodisks that may only intersect on their boundaries, and such that any point of the plane is contained in at most $k$ pseudodisks, it can be proven that $\chi(\mathcal{F})\le 3k/2 + o(k)$ since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudodisks are replaced by a family $\mathcal{F}$ of pseudosegments (a.k.a. strings) that do not cross. In other words, any two strings of $\mathcal{F}$ are only allowed to "touch" each other. Such a family is said to be $k$touching if no point of the plane is contained in more than $k$ elements of $\mathcal{F}$. We give bounds on $\chi(\mathcal{F})$ as a function of $k$, and in particular we show that $k$touching segments can be colored with $k+5$ colors. This partially answers a question of Hliněný (1998) on the chromatic number of contact systems of strings.