AAM  >> Vol. 3 No. 2 (May 2014)

    Upper Bound for the Number of Vertices of Color-Critical Graphs on Surfaces

  • 全文下载: PDF(480KB) HTML    PP.49-53   DOI: 10.12677/AAM.2014.32008  
  • 下载量: 1,926  浏览量: 5,985   国家自然科学基金支持


李青青,晁福刚,路伟华,任 韩:华东师范大学数学系,上海

嵌入亏格着色色临界图Embedding Genus Coloring Color-Critical Graph


Dirac观察到:对每个固定的曲面S和每个固定的自然数k ≥ 8,曲面S上仅有有限多个k-色临界图。MoharThomassen证明了:对于亏格g ≥ 2的曲面S,曲面S上的7-色临界图的点数少于138(g ‒ 1)。我们借助于Euler公式和Gallai所发展起来的研究色临界图的方法,改进了这个结果,给出了曲面S上的7-色临界图的个数是有限的一个比较简洁的证明。除此以外,我们还给出曲面S上的每一个k-色临界图(k ≥ 7)的点数上界的一个统一的表达式。
Dirac observed that, for each fixed surface and each natural number k ≥ 8, there are only finitely many k-color-critical graphs on S. Mohar and Thomassen proved that for a surface S of genus g ≥ 2, every 7-color-critical graph on S has less than 138(g ‒ 1) vertices. Using Euler formula and the critical-graphs methods of Gallai, we improve this result and give a simple proof that the number of 7-color-critical graphs is finite. We also give unified expression for an upper bound of vertices of k-color-critical graphs (k ≥ 7) on surfaces.

李青青, 晁福刚, 路伟华, 任韩. 曲面上色临界图点数的上界[J]. 应用数学进展, 2014, 3(2): 49-53. http://dx.doi.org/10.12677/AAM.2014.32008


[1] Möbius, A.F. (1861) Zur theorie der polyëder und elementarverwandtschaft. Qeuvres Complètes, 2, 519-559.
[2] Jordan, C. (1866) Sur la déormation des surfaces. Journal de Mathématiques Pures et Appliquées, 11, 105-109.
[3] Thomassen, C. (1992) The Jordan-Schönflies theorem and the classification of surfaces. The American Mathematical Monthly, 99, 116-130.
[4] Euler, L. (1752) Elementa doctrinae solidorum. Demonstratio nonnullarum insignium proprietatum. Novi Comment Acad. Sc. Imp. Petropol., 4, 109-160.
[5] Edmonds, J.R. (1960) A combinatorial representation for polyhedral surfaces. Notices of the AMS—American Mathematical Society, 7, 646.
[6] Heffter, L. (1891) Über das problem der nachbargebiete. Mathematische Annalen, 38, 477-508.
[7] Heawood, P.J. (1890) Map colour theorem. The Quarterly Journal of Pure and Applied Mathematics, 24, 332-338.
[8] Ringel, G. and Youngs, J.W.T. (1968) Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences of the USA, 60, 438-455.
[9] Franklin, P. (1934) A six color problem. Journal of Mathematical Physics, 13, 363-369.
[10] Dirac, G.A. (1952) Map color theorem. Canadian Journal of Mathematics, 4, 480-490.
[11] Albertson, M.O. and Hutchinson, J.P. (1977) The independence ratio and genus of a graph. Transactions of the American Mathematical Society, 226, 161-173.
[12] Gimbel, J. and Thomassen, C. (1997) Coloring graphs with fixed genus and girth. Transactions of the American Mathematical Society, 349, 4555-4564.
[13] Dirac, G.A. (1953) The coloring of maps. Journal of the London Mathematical Society, 28, 476-480.
[14] Mohar, B. and Thomassen, C. (2001) Graphs on surfaces. Johns Hopkins University Press, London.
[15] Gallai, T. (1963) Kritische graphen I, II. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 8, 165-192,373-395.
[16] Thomassen, C. (1994) Five-coloring graphs on the torus. Journal of Combinatorial Theory, Series B, 62, 11-33.
[17] 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.
[18] 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.