Quadrangular embeddings of complete graphs and the Even Map Color Theorem (with details)

Abstract

Hartsfield and Ringel constructed orientable quadrangular embeddings of the complete graph $K_n$ for $n\equiv 5(\mathrm{mod}8)$, and nonorientable ones for $n\ge 9$ and $n\equiv 1(\mathrm{mod}4)$. These provide minimal quadrangulations of their underlying surfaces. We extend these results to determine, for every complete graph $K_n$, $n\ge 4$, the minimum genus, both orientable and nonorientable, for the surface in which $K_n$ has an embedding with all faces of degree at least $4$, and also for the surface in which $K_n$ has an embedding with all faces of even degree. These last embeddings provide sharpness examples for a result of Hutchinson bounding the chromatic number of graphs embedded with all faces of even degree, completing the proof of the Even Map Color Theorem. We also show that if a connected simple graph $G$ has a perfect matching and a cycle then the lexicographic product $G[K_4]$ has orientable and nonorientable quadrangular embeddings; this provides new examples of minimal quadrangulations.

Version 3 is a minor update to version 2, which was a major revision of version 1. Versions 2 and 3 contain details omitted from the published version. For version 3, Lemma 5.4 has been generalized and the proof simplified, and we now cite the published version of the paper. 26 pages; 6 figures