Map Coloring

Ringel-Youngs

If a surface is partitioned into contiguous regions, how many colors are required to complete a map, such that no two adjacent regions are the same color. On the sphere the answer is 4. But for surfaces of higher genus, the upper bound is

\gamma (g)=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor

For an orientable surface, the genus g, is the number of holes. So for a torus, a surface with one hole, the formula says at most 7 colors are needed. The next question is do the maximal maps exist. In 1968, Ringel and Youngs showed that they do.

Map requiring 12 colors on a surface with 6 holes. Has order three rotational symmetry and front-back symmetry

Fifteen color map on a surface with eleven holes. Order five symmetry and front-back symmetry. Regions fall into two categories. Ones which are symmetric on flip, and pairs which are swapped on flip.

Seven color map on surface with one hole. Modeled in Maya.

Map requiring 19 colors on a surface with 20 holes. Hand drew this thirty years ago.
The solution is the same family as the 7 color map on the torus. All regions are identical

Map requiring 7 colors on surface with one hole (torus). Has seven-fold rotational symmetry around the hole, as well as rotational symmetry perpendicular to the hole. Edges are arranged such that all the relationships can be viewed from one side.