Quadrangular embeddings of complete graphs and the Even Map Color Theorem
Quadrangular embeddings of complete graphs and the Even Map Color Theorem
复制标题
完全图的四边形嵌入和偶图颜色定理
DOI：
10.1016/j.jctb.2019.02.006
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
X. Zha
中科院分区：
文献类型：
--
作者：
Wenzhong Liu;S. Lawrencenko;Beifang Chen;M. Ellingham;N. Hartsfield;Hui Yang;D. Ye;X. Zha
Hartsfield和Ringel构造了完全图Kn的可定向四边形嵌入（n ≥ 5（mod 8））和不可定向四边形嵌入（n≥ 9，n ≥ 1（mod 4））.这些提供了其底层表面的最小四边形。我们推广了这些结果，对每个完全图Kn，n≥ 4，确定了Kn有一个嵌入的所有面的度至少为4的曲面和Kn有一个嵌入的所有面的度为偶数的曲面的最小亏格，包括可定向的和不可定向的亏格.这些最后的嵌入提供了清晰的例子，哈钦森边界的着色数的结果嵌入的所有面的偶数度，完成证明的偶映射颜色定理。我们还证明了，如果一个连通简单图G有一个完美匹配和一个圈，则字典序积G [K 4]有可定向和不可定向的四边形嵌入，这为极小四边形剖分提供了新的例子.
Hartsfield and Ringel constructed orientable quadrangular embeddings of the complete graph K n for n≡ 5 (mod 8), and nonorientable ones for n≥ 9 and n≡ 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.
将其他曲面四边形化的平面三角剖分
DOI：
--
发表时间：
2004
期刊：
European J. Combin. 25
影响因子：
--
作者：
F.Hiai;X.Zhan;M.Aikawa;T.Kawai;A.Nakamoto
通讯作者：
A.Nakamoto