点击次数：

所属单位：理学院

发表刊物：JOURNAL OF COMBINATORIAL THEORY SERIES B

关键字：Quadrangular embedding Complete graph Minimal quadrangulation 4-genus Even-faced embedding Map coloring Chromatic number

摘要：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号：0095-8956

是否译文：否

发表时间：2019-11-01

合写作者：Lawrencenko, Serge,Chen, Beifang,Ellingham, M. N.,Hartsfield, Nora,Yang, Hui,Ye, Dong,Zha, Xiaoya

通讯作者：Ellingham, M. N.,刘文忠