Quadrangular embeddings of complete graphs and the Even Map Color Theorem

摘要

Hartsfield and Ringel constructed orientable quadrangular embeddings of the complete graph K-n for n (math) 5 (mod 8), and nonorientable ones for n >= 9 and n (math) 1 (mod 4). These provide minimal quadrangulations of their underlying surfaces. We extend these results to determine, for every complete graph K-n, n >= 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. (C) 2019 Elsevier Inc. All rights reserved.