八个点的极小非环面图
Minimal Nontoroidal Graphs on Eight Vertices
DOI: 10.12677/AAM.2013.24025, PDF, HTML,    国家自然科学基金支持
作者: 晁福刚, 任 韩：华东师范大学数学系，上海
关键词: 嵌入；亏格；极小非环面图；Embedding; Genus; Minimal Nontoroidal Graph
摘要: 借助于嵌入的技巧，证明了由K8，八个点的完全图，去掉K3，三角形，或K2,3，部集的点数为2和3的完全二部图，或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.
文章引用：晁福刚, 任韩. 八个点的极小非环面图[J]. 应用数学进展, 2013, 2(4): 186-190. http://dx.doi.org/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.

为你推荐