Hits:

Affiliation of Author(s):理学院

Title of Paper:Quadrangular embeddings of complete graphs and the Even Map Color Theorem

Journal:JOURNAL OF COMBINATORIAL THEORY SERIES B

Key Words:Quadrangular embedding Complete graph Minimal quadrangulation 4-genus Even-faced embedding Map coloring Chromatic number

Abstract: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.

ISSN No.:0095-8956

Translation or Not:no

Date of Publication:2019-11-01

Co-author:Lawrencenko, Serge,Chen, Beifang,Ellingham, M. N.,Hartsfield, Nora,Yang, Hui,Ye, Dong,Zha, Xiaoya

Correspondence Author:Ellingham, M. N.,Wenzhong Liu