Minimum Size of Feedback Vertex Sets of Planar Graphs of Girth at least Five

preprint2016arXivOpen access

Abstract

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 GG is a connected planar graph of girth at least five on nn vertices and mm edges, then GG has a feedback vertex set of size at most 2m−n+27\frac{2m-n+2}{7}. By Euler's formula, this implies that GG has a feedback vertex set of size at most m5\frac{m}{5} and n−23\frac{n-2}{3}. These results not only improve a result of Dross, Montassier and Pinlou and confirm the girth-5 case of one of their conjectures, but also make the best known progress towards a conjecture of Kowalik, Lužar and Škrekovski and solves 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.