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
Tomáš Madaras
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.
- J. Bensmail, On \(q\)-power cycles in cubic graphs, Discuss. Math. Graph Theory 37 (2017), 211-220.
- 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].
- G. Exoo, Three graphs and the Erdös-Gyárfás conjecture, arXiv:1403.5636 [math.CO].
- C.C. Heckman, R. Krakovski, Erdös-Gyárfás conjecture for cubic planar graphs, Electron. J. Combin. 20 (2013) P7.
- 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.
- A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Čas. SAV (Math. Slovaca) 5 (1955), 101-113.
- T. Madaras, M. Tamášová, Minimal unavoidable sets of cycles in polyhedral graphs, manuscript.
- P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904), 413-426.
- D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.
- Tomáš Madaras
- 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.
- Received: 2017-11-28.
- Revised: 2018-06-08.
- Accepted: 2018-06-08.
- Published online: 2018-07-05.
