八个点的极小非环面图
Minimal Nontoroidal Graphs on Eight Vertices

作者: 晁福刚 , 任 韩 :华东师范大学数学系,上海;

关键词: 嵌入亏格极小非环面图Embedding Genus Minimal Nontoroidal Graph

摘要:
借助于嵌入的技巧,证明了由K8,八个点的完全图,去掉K3,三角形,或K2,3,部集的点数为23的完全二部图,或K2∪K2∪P3,长度为1的两条路和长度为2的一条路的不交并,中的边得到的图是极小的非环面图。

Abstract:
Using the technique of embedding, we prove that the graphs obtained fromK8 , the complete graph on eight vertices, by deleting the edges ofK3 , a triangle, orK2,3 , the complete bipartite graph with 2 vertices and 3 vertices, orK2∪K2∪P3 , the disjoint union of two paths of length one and one path of length two, are minimal nontoroidal graphs.

文章引用: 晁福刚 , 任 韩 (2013) 八个点的极小非环面图。 应用数学进展, 2, 186-190. doi: 10.12677/AAM.2013.24025

参考文献

[1] Thomassen, C. (1992) The Jordan-Schönflies theorem and the classification of surfaces. American Mathematical Monthly, 99, 116-130.

[2] Mohar, B. and Thomassen, C. (2001) Graphs on surfaces. Johns Hopkins University Press, London.

[3] Kuratowski, C. (1930) Sur le probléme des courbes gauches en topologie. Fundamenta Mathematicae, 15, 271-283.

[4] Heawood, P.J. (1890) Map colour theorem. The Quarterly Journal of Pure and Applied Mathematics, 24, 332-338.

[5] Ringel, G. and Youngs, J.W.T. (1968) Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences of the United States of America, 60, 438-455.

[6] Franklin, P. (1934) A six color problem. Journal of Mathematical Physics, 13, 363-369.

[7] Rringel, G. (1974) Map color theorem. Springer, Berlin.

[8] Thomassen, C. (1989) The graph genus problem is NP-complete. Journal of Algorithms, 10, 568-576.

[9] Thomassen, C. (1993) Five-coloring maps on surfaces. Journal of Combinatorial Theory, Series B, 59, 89-105.

[10] Thomassen, C. (1997) Color-critical graphs on a fixed surface. Journal of Combinatorial Theory, Series B, 70, 67-100.

[11] Thomassen, C. (2003) The chromatic number of a graph of girth 5 on a fixed surface. Journal of Combinatorial Theory, Series B, 87, 38-71.

[12] Chenette, N., Postle, L., Streib, N. and Thomas, R. (2012) Five-colorings graphs on the Klein bottle. Journal of Combinatorial Theory, Series B, 102, 1067-1098.

[13] Kawarayabashi, K.I., Král, D., Kynčl, J. and Lidický, B. (2009) 6-critical graphs on the Klein bottle. SIAM Journal on Discrete Mathematics, 23, 372-383.

分享
Top