Note on $4$-coloring $6$-regular triangulations on the torus

Abstract

In 1973, Altshuler characterized the $6$-regular triangulations on the torus to be precisely those that are obtained from a regular triangulation of the $r\times s$ toroidal grid where the vertices in the first and last column are connected by a shift of $t$ vertices. Such a graph is denoted $T(r,s,t)$. In 1999, Collins and Hutchinson classified the $4$-colorable graphs $T(r,s,t)$ with $r,s\ge 3$. In this paper, we point out a gap in their classification and show how it can be fixed. Combined with the classification of the $4$-colorable graphs $T(1,s,t)$ by Yeh and Zhu in 2003, this completes the characterization of the colorability of all the $6$-regular triangulations on the torus.

arXiv comment9 pages, 1 figure

References in corpus (1)

• The choice number versus the chromatic number for graphs embeddable on orientable surfaces