Minimum size of feedback vertex sets of planar graphs of girth at least five

DOI10.1016/J.EJC.2016.10.009zbMATH Open1352.05057OpenAlexW2301667118MaRDI QIDQ730261FDOQ730261

Authors Tom Kelly, Chun-Hung Liu 

Publication date 27 December 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.04559

zbMATH Keywords

decycling numberinduced forestforest number

Mathematics Subject Classification ID

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

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 $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 $frac2m-n+27$. By Euler's formula, this implies that $G$ has a feedback vertex set of size at most $fracm5$ and $fracn-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, Luv{z}ar and v{S}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.

Recommendations

• A lower bound on the order of the largest induced forest in planar graphs with high girth
• Feedback vertex set on planar graphs
• Small feedback vertex sets in planar digraphs
• On cycle packings and feedback vertex sets
• Minimum feedback vertex set and acyclic coloring.

Cites work

• scientific article; zbMATH DE number 3565019 (Why is no real title available?)
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• An improved bound on the largest induced forests for triangle-free planar graphs
• Large induced forests in sparse graphs
• Large induced forests in triangle-free planar graphs
• The decycling number of regular graphs

Cited in

(17)

• Feedback vertex set on planar graphs
• Splitting plane graphs to outerplanarity
• Maximum induced forests of product graphs
• Size of the largest induced forest in subcubic graphs of girth at least four and five
• Feedback vertex number of Sierpiński-type graphs
• MIP formulations for induced graph optimization problems: a tutorial
• Large induced forests in planar graphs with girth 4
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• The size of graphs with given feedback vertex number
• Splitting plane graphs to outerplanarity
• Small feedback vertex sets in planar digraphs
• Cycle isolation of graphs with small girth
• 3‐Degenerate induced subgraph of a planar graph
• On cycle packings and feedback vertex sets
• Induced 2-degenerate subgraphs of triangle-free planar graphs
• Robust connectivity of graphs on surfaces
• Partial DP-coloring of graphs

This page was built for publication: Minimum size of feedback vertex sets of planar graphs of girth at least five

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730261)