Coloring a set of touching strings

Louis Esperet 1 Daniel Gonçalves 2 Arnaud Labourel 3
1 G-SCOP_OC - OC
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.
Type de document :
Communication dans un congrès
EuroComb'09: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. Elsevier, 34, pp.213-217, 2009, Electronic Notes in Discrete Mathematics
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00433096
Contributeur : Daniel Gonçalves <>
Soumis le : mercredi 18 novembre 2009 - 10:48:12
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00433096, version 1

Citation

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. Elsevier, 34, pp.213-217, 2009, Electronic Notes in Discrete Mathematics. 〈lirmm-00433096〉

Partager

Métriques

Consultations de la notice

218