Coloring non-crossing strings (Q727171): Difference between revisions

Summary: For a family \(\mathcal{F}\) of geometric objects in the plane, 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 pseudo-disks that may only intersect on their boundaries, and such that any point of the plane is contained in at most \(k\) pseudo-disks, it can be proven that \(\chi(\mathcal{F})\leq 3k/2 + o(k)\) since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudo-disks are replaced by a family \(\mathcal{F}\) of pseudo-segments (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 \textit{P. Hliněný} [Discrete Appl. Math. 81, No. 1--3, 59--68 (1998; Zbl 0898.05025)] on the chromatic number of contact systems of strings.