Skip to Main content Skip to Navigation

On edge tricolorations of triangulations of simply connected surfaces

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:08:24 AM
Last modification on : Saturday, September 11, 2021 - 3:19:18 AM


Files produced by the author(s)


  • HAL Id : hal-02101862, version 1



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⟩



Les métriques sont temporairement indisponibles