×

Minimum size of feedback vertex sets of planar graphs of girth at least five. (English) Zbl 1352.05057

Summary: A feedback vertex set of a graph is a subset of vertices intersecting all cycles. We provide tight upper bounds on the size of a minimum feedback vertex set in planar graphs of girth at least five. We prove that if \(G\) is a connected planar graph of girth at least five on \(n\) vertices and \(m\) edges, then \(G\) has a feedback vertex set of size at most \(\frac{2m-n+2}{7}\). By Euler’s formula, this implies that \(G\) has a feedback vertex set of size at most \(\frac{m}{5}\) and \(\frac{n-2}{3}\). These results not only improve a result of F. Dross et al. [Discrete Appl. Math. 214, 99–107 (2016; Zbl 1346.05039)] and confirm the girth-5 case of one of their conjectures, but also make the best known progress towards a conjecture of L. Kowalik et al. [Discrete Math. Theor. Comput. Sci. 12, No. 1, 87–100 (2010; Zbl 1250.05041)] and solve the subcubic case of their conjecture. An important step of our proof is providing an upper bound on the size of minimum feedback vertex sets of subcubic graphs with girth at least five with no induced subdivision of members of a finite family of non-planar graphs.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory

References:

[1] Albertson, M. O.; Berman, D. M.: A conjecture on planar graphs. Graph theory and related topics (1979)
[2] Alon, N.; Mubayi, D.; Thomas, R.: Large induced forests in sparse graphs. J. graph theory 38, 113-123 (2001) · Zbl 0986.05060 · doi:10.1002/jgt.1028
[3] Borodin, O. V.: A proof of B. Grünbaum’s conjecture on the acyclic 5-colorability of planar graphs. Dokl. akad. Nauk SSSR 231, 18-20 (1976) · Zbl 0363.05031
[4] F. Dross, M. Montassier, A. Pinlou, Large induced forests in planar graphs with girth 4 or 5, arXiv:1409.1348. · Zbl 1346.05228
[5] Dross, F.; Montassier, M.; Pinlou, A.: A lower bound on the order of the largest induced forest in planar graphs with high girth. Discrete appl. Math. 214, 99-107 (2016) · Zbl 1346.05039 · doi:10.1016/j.dam.2016.06.011
[6] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972, pp. 85-103.
[7] T. Kelly, C.-H. Liu, Size of the largest induced forest in subcubic graphs of girth at least four and five, arXiv:1603.03855.
[8] Kowalik, ł.; Lužar, B.; Škrekovski, R.: An improved bound on the largest induced forests for triangle-free planar graphs. Discrete math. Theor. comput. Sci. 12, 87-100 (2010) · Zbl 1250.05041
[9] Punnim, N.: The decycling number of regular graphs. Thai J. Math. 4, 145-161 (2006) · Zbl 1156.05317
[10] Salavatipour, M. R.: Large induced forests in triangle-free planar graphs. Graphs combin. 22, 113-126 (2006) · Zbl 1092.05020 · doi:10.1007/s00373-006-0642-7
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.