Opuscula Math. 38, no. 6 (2018), 859-870
https://doi.org/10.7494/OpMath.2018.38.6.859

Opuscula Mathematica

# Minimal unavoidable sets of cycles in plane graphs

Martina Tamášová

Abstract. A set $$S$$ of cycles is minimal unavoidable in a graph family $$\cal{G}$$ if each graph $$G \in \cal{G}$$ contains a cycle from $$S$$ and, for each proper subset $$S^{\prime}\subset S$$, there exists an infinite subfamily $$\cal{G}^{\prime}\subseteq\cal{G}$$ such that no graph from $$\cal{G}^{\prime}$$ contains a cycle from $$S^{\prime}$$. In this paper, we study minimal unavoidable sets of cycles in plane graphs of minimum degree at least 3 and present several graph constructions which forbid many cycle sets to be unavoidable. We also show the minimality of several small sets consisting of short cycles.

Keywords: plane graph, polyhedral graph, set of cycles.

Mathematics Subject Classification: 05C10.

Full text (pdf)

1. J. Bensmail, On $$q$$-power cycles in cubic graphs, Discuss. Math. Graph Theory 37 (2017), 211-220.
2. O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Math. Notes 46 (1989), 835-837 (English translation), Mat. Zametki 46 (1989), 9-12 [in Russian].
3. G. Exoo, Three graphs and the Erdös-Gyárfás conjecture, arXiv:1403.5636 [math.CO].
4. C.C. Heckman, R. Krakovski, Erdös-Gyárfás conjecture for cubic planar graphs, Electron. J. Combin. 20 (2013) P7.
5. S. Jendrol', P.J. Owens, On light graphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs and Combinatorics 17 (2001) 4, 659-680.
6. A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Čas. SAV (Math. Slovaca) 5 (1955), 101-113.
7. T. Madaras, M. Tamášová, Minimal unavoidable sets of cycles in polyhedral graphs, manuscript.
8. P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904), 413-426.
9. D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.
• Pavol Jozef Šafárik University, Faculty of Science, Institute of Mathematics, Jesenná 5, 04001 Košice, Slovakia
• Martina Tamášová
• Pavol Jozef Šafárik University, Faculty of Science, Institute of Mathematics, Jesenná 5, 04001 Košice, Slovakia
• Communicated by Ingo Schiermeyer.
• Revised: 2018-06-08.
• Accepted: 2018-06-08.
• Published online: 2018-07-05.