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 :
Reports
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101862
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:24 AM
Last modification on : Sunday, May 19, 2019 - 1:20:43 AM

File

RR2002-22.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101862, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

2

Files downloads

7