Advances in Applied Mathematics
Vol.3 No.02(2014), Article ID:13470,4 pages DOI:10.12677/AAM.2014.32008

Qingqing Li, Fugang Chao, Weihua Lu, Han Ren

Department of Mathematics, East China Normal University, Shanghai

Email: chaofugang@126.com, hren@math.ecnu.edu.cn

Copyright © 2014 by authors and Hans Publishers Inc.

Received: Mar. 18th, 2014; revised: Apr. 16th, 2014; accepted: Apr. 22nd, 2014

ABSTRACT

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.

Keywords:Embedding, Genus, Coloring, Color-Critical Graph

Dirac观察到：对每个固定的曲面S和每个固定的自然数k ≥ 8，曲面S上仅有有限多个k-色临界图。Mohar和Thomassen证明了：对于亏格g ≥ 2的曲面S，曲面S上的7-色临界图的点数少于138(g ‒ 1)。我们借助于Euler公式和Gallai所发展起来的研究色临界图的方法，改进了这个结果，给出了曲面S上的7-色临界图的个数是有限的一个比较简洁的证明。除此以外，我们还给出曲面S上的每一个k-色临界图(k ≥ 7)的点数上界的一个统一的表达式。

1. 引言

2. 主要定理及其证明

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.