Coloring a set of touching strings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

Coloring a set of touching strings

Louis Esperet


For a family F of geometric objects in the plane, define the X(F) as the least integer ℓ such that the elements of F can be colored with ℓ colors, in such a way that any two intersecting objects have distinct colors. When F is a set of Jordan regions that may only intersect on their boundaries, and such that any point of the plane is contained in at most k regions, it can be proven that X(F)<3k/2 +o(k) since the problem is equivalent to cyclic coloring of plane graphs [O. Amini, L. Esperet, and J. van den Heuvel, A Unified Approach to Distance-Two Colouring of Planar Graphs, In: Proc. 20th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA09), ACM Press, New-York (2009)]. In this paper, we study the same problem when Jordan regions are replaced by Jordan curves that do not cross (two curves are only allowed to "touch" each other). We conjecture that also in this case, X(F) is bounded by ck for some c>0. To support this conjecture, we prove it when the curves are x-monotone (any vertical line intersect each curve at most once), and we give a bound in the general case that also depends on how many times two curves intersect.
No file

Dates and versions

lirmm-00433096 , version 1 (18-11-2009)


  • HAL Id : lirmm-00433096 , version 1


Louis Esperet, Daniel Gonçalves, Arnaud Labourel. Coloring a set of touching strings. EuroComb'09: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. pp.213-217. ⟨lirmm-00433096⟩
182 View
0 Download


Gmail Mastodon Facebook X LinkedIn More