ARTICLE
TITLE

Coloring Non-Crossing Strings

SUMMARY

For a family of geometric objects in the plane F={S1,…,Sn}\mathcal{F}=\{S_1,\ldots,S_n\}, define ?(F)\chi(\mathcal{F}) as the least integer l\ell such that the elements of F\mathcal{F} can be colored with l\ell colors, in such a way that any two intersecting objects have distinct colors. When F\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 kk pseudo-disks, it can be proven that ?(F)=3k/2+o(k)\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 pseudo-disks are replaced by a family F\mathcal{F} of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of F\mathcal{F} are only allowed to "touch" each other. Such a family is said to be kk-touching if no point of the plane is contained in more than kk elements of F\mathcal{F}. We give bounds on ?(F)\chi(\mathcal{F}) as a function of kk, and in particular we show that kk-touching segments can be colored with k+5k+5 colors. This partially answers a question of Hlinený (1998) on the chromatic number of contact systems of strings.

 Articles related

Sandro Rajola, Maria Scafati Tallini    

We call planar space a triple (S,L,P), where (S,L) is a finite linear space non reduced to a line and P is a family of proper subspaces of (S,L), called planes, such that every plane contains three non-collinear points and through three non-collinear poi... see more

Revista: Le Matematiche

Michela Artebani, Remke Kloosterman, Marco Pacini    

In this paper we give a birational model for the theta divisor of the intermediate Jacobian of a generic cubic threefold X . We use the standard realization of X as a conic bundle and a 4-dimensional family of plane quartics which are totally tangent to ... see more

Revista: Le Matematiche

Giulio Santoro    

The family of systems of parabolic cylinder, point and plane in A_3, proves to be measurable.

Revista: Le Matematiche

L. Fraizer    

Worldwide efforts—such as Sustainable Development Goals and its predecessor Millennium Development Goals—historically offers country policy makers, industry leaders, and proactive citizens an aspirational guiding charter for actions needed to address com... see more

Revista: Invotec

Ioannis K. Argyros, Dong Chen    

We study the Ostrowski-Kantorovich convergence for a family of Halley- Werner type iteration methods in the complex plane. We provide an upper error bound for all parameter ? ? [1 , 2). We show that the error bound is a decreasing function of ?. We prove... see more

Revista: Proyecciones