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

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)$.