Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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⟩



Record views


Files downloads