TY - JOUR
T1 - Minimum size of feedback vertex sets of planar graphs of girth at least five
AU - Kelly, Tom
AU - Liu, Chun Hung
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2017/3/1
Y1 - 2017/3/1
N2 - 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 2m−n+27. By Euler's formula, this implies that G has a feedback vertex set of size at most m5 and n−23. 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 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.
AB - 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 2m−n+27. By Euler's formula, this implies that G has a feedback vertex set of size at most m5 and n−23. 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 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.
UR - http://www.scopus.com/inward/record.url?scp=84997181508&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84997181508&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2016.10.009
DO - 10.1016/j.ejc.2016.10.009
M3 - Article
AN - SCOPUS:84997181508
SN - 0195-6698
VL - 61
SP - 138
EP - 150
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -