×

zbMATH — the first resource for mathematics

Islands in graphs on surfaces. (English) Zbl 1329.05105

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] N. Alon, G. Ding, B. Oporowski, and D. Vertigan, Partitioning into graphs with only small components, J. Combin. Theory Ser. B, 87 (2003), pp. 231–243. · Zbl 1023.05045
[2] M. Axenovich, T. Ueckerdt, and P. Weiner, Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths, preprint, http://arxiv.org/abs/1507.02815arXiv:1507.02815, 2015. · Zbl 1367.05044
[3] O. V. Borodin, A. V. Kostochka, and M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Math., 313 (2013), pp. 2638–2649. · Zbl 1281.05060
[4] G. Chappell and J. Gimbel, On subgraphs without large components, Math. Bohem., to appear. · Zbl 1424.05076
[5] W. Cushing and H. A. Kierstead, Planar graphs are 1-relaxed, 4-choosable, European J. Combin., 31 (2012), pp. 1385–1397. · Zbl 1221.05077
[6] L. Esperet and G. Joret, Coloring planar graphs with three colors and no large monochromatic components, Combin. Probab. Comput., 23 (2014), pp. 551–570. · Zbl 1334.05030
[7] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 8 (1959), pp. 109–120.
[8] P. Haxell, T. Szabó, and G. Tardos, Bounded size components–partitions and transversals, J. Combin. Theory Ser. B, 88 (2003), pp. 281–297. · Zbl 1033.05083
[9] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic \(\le 0\)—a survey, in Paul Erdös and His Mathematics. II, Bolyai Soc. Math. Stud. 11, G. Halász, L. Lovász, M. Simonovits, and V. T. Sós, eds., Springer, Budapest, 2002, pp. 375–411. · Zbl 1037.05015
[10] S. Jendrol’ and H.-J. Voss, Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds, European J. Combin., 26 (2005), pp. 457–471. · Zbl 1077.05029
[11] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane—A survey, Discrete Math., 313 (2013), pp. 406–421. · Zbl 1259.05045
[12] K. Kawarabayashi and C. Thomassen, From the plane to higher surfaces, J. Combin. Theory Ser. B, 102 (2012), pp. 852–868. · Zbl 1244.05075
[13] J. Kleinberg, R. Motwani, P. Raghavan, and S. Venkatasubramanian, Storage management for evolving databases, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1997), 1997, pp. 353–362.
[14] N. Linial, J. Matoušek, O. Sheffet, and G. Tardos, Graph coloring with no large monochromatic components, Combin. Probab. Comput., 17 (2008), pp. 577–589. · Zbl 1171.05021
[15] L. Lovász, Coverings and colorings of hypergraphs, in Proceedings of the Fourth South-Eastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1973, pp. 3–12.
[16] B. Mohar and C. Thomassen, Graphs on Surfaces, The Johns Hopkins University Press, Baltimore, MD, 2001. · Zbl 0979.05002
[17] C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B, 62 (1994), pp. 180–181. · Zbl 0805.05023
[18] M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math., 146 (1995), pp. 325–328. · Zbl 0843.05034
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.