Triangulations of the torus with at most two odd vertices: structure and coloring

Resource type
Thesis type
(Thesis) Ph.D.
Date created
This thesis consists of two parts. In the first part, we give a simple geometric description of the set $mathcal G(5,5,8)$ of toroidal triangulations, all of whose vertices have degree six, except for two of degree five and one of degree eight. The motivation for studying such family is provided by Gr"unbaum coloring application described below. Each such triangulation is described by a cut-and-glue construction starting from an infinite triangular grid. In particular, we show that the members of $mathcal G(5,5,8)$ are obtained from a toroidal 6-regular graph (three parameters) by cutting out a special disk, described with two parameters, and ``stitching" along the cut. To achieve that, we develop some techniques and define some invariants to study the cycles of toroidal triangulations. We also introduce some special triangulated disks called ``blocks" and show how to detect their presence in a triangulation. Then, we show the existence of a special path that identifies the ``cut". Also, the graphs in $mathcal G(5,5,8)$ are classified into several families, based on the existence of some special cycles, containing a vertex of degree eight. Each family is, further, described by a schema for gluing together a few blocks. The second part regards coloring. A Gr"unbaum coloring of a graph $G$ which triangulates a surface is a 3-edge-coloring of $G$ in which every face is incident to three edges of different colors. In 1968 Gr"unbaum conjectured a generalization of the Four Color Theorem: every simple triangulation of every orientable surface has a Gr"unbaum coloring. In 2008 Kochol discovered counterexamples to Gr"unbaum's conjecture on every orientable surface of genus at least five. Gr"unbaum's conjecture is still believed to be true for the torus. We verify ``weak" Gr"unbaum conjecture for three families of triangulations in higher surfaces that, to our knowledge, are the only known families of triangulations with unbounded facewidth that are not 4-colorable. Also, as an application of our description, we propose a method by which to verify the Gr"unbaum's conjecture for $mathcal G(5,5,8)$.
Copyright statement
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Goddyn, Luis
Member of collection
Download file Size
etd6406_FVerdian-Rizi.pdf 1.11 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0