Skip to Main content Skip to Navigation
Conference papers

Coloring a set of touching strings

Louis Esperet 1 Daniel Gonçalves 2 Arnaud Labourel 3 
1 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Daniel Gonçalves Connect in order to contact the contributor
Submitted on : Wednesday, November 18, 2009 - 10:48:12 AM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM


  • 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⟩



Record views