On edge tricolorations of triangulations of simply connected surfaces

Olivier Bodini (1) , Eric Rémila (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

This paper studies the tricolorations of edges of triangulations of simply connected orientable surfaces such that the degree of each interior vertex is even. Using previous results on lozenge tilings, we give a linear algorithm of coloration for triangulations of the sphere, or of planar regions with the constraint that the boundary is monochromatic. We define a flip as a shift of colors on a cycle of edges using only two colors. We prove flip connectivity of the set of solutions for the cases seen above, and prove that there is no flip accessibility in the general case where the boundary is not assumed to be monochromatic. Nevertheless, using flips, we obtain a tiling invariant, even in the general case. We finish relaxing the condition, allowing monochromatic triangles. With this hypothesis, there exists some local flips. We give a linear algorithm of coloration, and strong structural results on the set of solutions.

Cet article étudie les tricolorations des arêtes des triangulations des surfaces simplement connexes orientables, telles que le degré de chaque sommet intérieur soit pair. A partir de résultats précédents sur les pavages par des losanges, nous donnons un algorithme linéaire de colorations pour les triangulations de la sphère, ou pour des régions du plan sous la contrainte que le bord est monochromatique. Nous définissons un flip comme étant une inversion des couleurs sur un cycle d’arêtes n’utilisant que deux couleurs. Nous prouvons la connexité par flips de l’ensemble des solutions dans les cas vus ci-dessus, et montrons que la connexité n’est pas toujours obtenue quand le bord n’est pas monochromatique. Néanmoins, grâce aux flips, nous avons un invariant de pavage, valable dans le cas général.Nous terminons en relâchant les conditions par l’introduction de tuiles monochromatiques. Dans ce cas, il existe des flips locaux.Nous donnons un algorithme linaire de colorations et des résultats structurels fors sur l’espace des solution

Mots clés: Flip; Height Function; Tiling

Mots clés: Pavage; Fonction de hauteur

Domaines: Informatique [cs]

Olivier Bodini, Eric Rémila. On edge tricolorations of triangulations of simply connected surfaces. [Research Report] LIP RR-2002-22, Laboratoire de l'informatique du parallélisme. 2002, 2+10p. ⟨hal-02101862⟩