Color-critical graphs on a fixed surface. (English) Zbl 0883.05051

A graph is \(k\)-color-critical if its vertex chromatic number is \(k\), but every proper subgraph is (\(k-1\))-colorable. It is known that for each orientable surface \(S\) and for each \(k \geq 7\), there are only finitely many \(k\)-color-critical graphs on \(S\). On the other hand, there are infinitely many 5-critical graphs on each surface \(S\) except the sphere.
In this paper the author shows that for each orientable surface \(S\) there are only finitely many 6-color-critical graphs on \(S\). He also shows that if \(k \geq 5\), then there exists a polynomially-bounded algorithm for deciding if a graph on \(S\) can be \(k\)-colored. The techniques involve cutting the surface and graph to transform it into a planar graph, then applying various 5-coloring results for planar graphs. Some extensions of the results are given where a small subgraph is pre-colored, to list colorings, and to non-orientable surfaces.


05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Albertson, M.O.; Stromquist, W.R., Locally planar toroidal graphs are 5-colorable, Proc. amer. soc., 84, 449-456, (1982) · Zbl 0518.05031
[2] Barnette, D., Coloring polyhedral manifolds, Discrete geometry and convexity, (1985), New York Acad. Sci · Zbl 0571.05018
[3] M. Borowieck, E. Drgas-Burchardt, P. Mihók, 1995, Generalized list colorings of graphs
[4] Battle, J.; Harary, F.; Kodama, Y.; Youngs, J.W.T., Additivity of the genus of a graph, Bull. amer. math. soc., 68, 565-568, (1962) · Zbl 0142.41501
[5] Croft, H.T.; Falconer, K.J.; Guy, R.K., Unsolved problems in geometry, (1991), Springer-Verlag · Zbl 0748.52001
[6] Dirac, G.A., The coloring of maps, J. London math. soc., 28, 476-480, (1953) · Zbl 0051.14702
[7] P. Erdös, A. L. Rubin, H. Taylor, Choosability in Graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, California, 5-7.9.1979
[8] Fisk, S., Geometric coloring theory, Advances math., 24, 298-340, (1979) · Zbl 0358.05023
[9] Fisk, S., The non-existence of colorings, J. combin. theory ser. B., 24, 247-248, (1978) · Zbl 0358.55002
[10] Gallai, T., Kritische graphen I, II, Publ. math. inst. hungar. acad. sci., 8, (1963) · Zbl 0121.18401
[11] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), W. H. Freeman San Francisco · Zbl 0411.68039
[12] J. Gimbel, C. Thomassen, Coloring graphs with bounded genus and girth, Trans. Amer. Math. Soc. · Zbl 0884.05039
[13] S. Gutner, The complexity of planar graph choosability · Zbl 0865.05066
[14] Jensen, T.; Toft, B., Graph coloring problems, (1995), J. Wiley New York · Zbl 0855.05054
[15] Stahl, S.; Beineke, L., Blocks and the nonorientable genus of a graph, J. graph theory, 1, 75-78, (1977) · Zbl 0366.05030
[16] Stromquist, W.R., The four color problem for locally planar graphs, ()
[17] Thomassen, C., Planarity and duality of finite and infinite graphs, J. combin. theory ser. B, 29, 244-271, (1980) · Zbl 0441.05023
[18] Thomassen, C., Embeddings of graphs with no short noncontractible cycles, J. combin. theory ser. B, 48, 155-177, (1990) · Zbl 0704.05011
[19] Thomassen, C., 5-coloring maps on surfaces, J. combin. theory ser. B, 59, 89-105, (1993) · Zbl 0794.05026
[20] Thomassen, C., Five-coloring graphs on the torus, J. combin. theory ser. B, 62, 11-33, (1994) · Zbl 0805.05022
[21] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[22] Voigt, M., List colourings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.