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)