zbMATH — the first resource for mathematics

From the plane to higher surfaces. (English) Zbl 1244.05075
Summary: We show that Grötzsch’s theorem extends to all higher surfaces in the sense that every triangle-free graph on a surface of Euler genus \(g\) becomes 3-colorable after deleting a set of at most \(1000 \cdot g\cdot f(g)\) vertices where \(f(g)\) is the smallest edge-width which guarantees a graph of Euler genus \(g\) and girth 5 to be 3-colorable.
We derive this result from a general cutting technique which we also use to extend other results on planar graphs to higher surfaces in the same spirit, even after deleting only \(1000g\) vertices. These include the 5-list-color theorem, results on arboricity, and various types of colorings, and decomposition theorems of planar graphs into two graphs with prescribed degeneracy properties.
It is not known if the 4-color theorem extends in this way.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Albertson, M.O., Open problem 2, (), 609
[2] Albertson, M.O.; Chappell, G.G.; Kierstead, H.A.; Kündgen, A.; Ramamurthi, R., Coloring with no 2-colored \(P_4\)ʼs, Electron. J. combin., 11, #R26, (2004) · Zbl 1053.05045
[3] Alon, N.; Ding, G.; Oporowski, B.; Vertigan, Partitioning into graphs with only small components, J. combin. theory ser. B, 87, 231-243, (2003) · Zbl 1023.05045
[4] Appel, K.; Haken, A., Every planar map is four colorable, Contemp. math., vol. 98, (1989), Amer. Math. Soc. Providence, RI · Zbl 0681.05027
[5] Borodin, O.V., On decomposition of graphs into degenerate subgraphs, Diskretn. anal., 28, 3-11, (1976) · Zbl 0425.05058
[6] Borodin, O.V., On acyclic colorings of planar graphs, Discrete math., 25, 211-236, (1979) · Zbl 0406.05031
[7] O.V. Borodin, A.N. Glebov, On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph (in Russian), Diskretn. Anal. Issled. Oper. Ser. 1. · Zbl 1012.05133
[8] S. Cabello, E.W. Chambers, Mutiple source shortest paths in a genus g graph, in: Proceeding of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 89-97. · Zbl 1302.05090
[9] DeVos, M.; Kawarabayashi, K.; Mohar, B., Locally planar graphs are 5-choosable, J. combin. theory ser. B, 98, 1215-1232, (2008) · Zbl 1187.05030
[10] Z. Dvorák, D. Králʼ, R. Thomas, private communication, 2007.
[11] Gimbel, J.; Thomassen, C., Coloring graphs with fixed genus and girth, Trans. amer. math. soc., 349, 4555-4564, (1997) · Zbl 0884.05039
[12] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. math., 14, 390-408, (1973) · Zbl 0265.05103
[13] Kawarabayashi, K.; Mohar, B., Star colorings and acyclic colorings of locally planar graphs, SIAM J. discrete math., 24, 56-71, (2010) · Zbl 1215.05068
[14] Kawarabayashi, K.; Thomassen, C., Decomposing a planar graph of girth 5 into an independent set and a forest, J. combin. theory ser. B, 99, 674-684, (2009) · Zbl 1184.05029
[15] Kowalik, L., Fast 3-coloring triangle-free planar graphs, (), 435-447 · Zbl 1111.68589
[16] A. Labourel, Edge-disjoint spanning trees in triangulated graphs on surfaces and application to node labeling, manuscript, 2006.
[17] Mohar, B., Acyclic colorings of locally planar graphs, European J. combin., 26, 491-503, (2005) · Zbl 1058.05024
[18] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore · Zbl 0979.05002
[19] Robertson, N.; Sanders, D.; Seymour, P.D.; Thomas, R., The four-colour theorem, J. combin. theory ser. B, 70, 2-44, (1997) · Zbl 0883.05056
[20] Thomassen, C., Five-coloring maps on surfaces, J. combin. theory ser. B, 59, 89-105, (1993) · Zbl 0794.05026
[21] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[22] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[23] Thomassen, C., Decomposing a planar graph into degenerate graphs, J. combin. theory ser. B, 65, 305-314, (1995) · Zbl 0840.05070
[24] Thomassen, C., Decomposing a planar graph into an independent set and a 3-degenerate graph, J. combin. theory ser. B, 83, 262-271, (2001) · Zbl 1024.05075
[25] Thomassen, C., A short List color proof of grötzschʼs theorem, J. combin. theory ser. B, 88, 189-192, (2003) · Zbl 1025.05022
[26] Thomassen, C., The chromatic number of a graph of girth 5 on a fixed surface, J. combin. theory ser. B, 87, 38-71, (2003) · Zbl 1020.05030
[27] 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.