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

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

Tom Kelly, Chun-Hung Liu

Publication date: 27 December 2016

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

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.

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

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.

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)

Cites Work

• Large induced forests in sparse graphs
• Title not available (Why is that?)
• Large induced forests in triangle-free planar graphs
• A lower bound on the order of the largest induced forest in planar graphs with high girth
• Title not available (Why is that?)
• The decycling number of regular graphs
• Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

Cited In (14)

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

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)