pith. sign in

arxiv: 1606.04419 · v3 · pith:D6DNQXAPnew · submitted 2016-06-14 · 🧮 math.CO

Small feedback vertex sets in planar digraphs

classification 🧮 math.CO
keywords directedtfraccycleplanarverticescontainsdigraphsfeedback
0
0 comments X
read the original abstract

Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $g\ge 4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|\le \tfrac{5n-5}9$ if $g=4$, $|X|\le \tfrac{2n-5}4$ if $g=5$, and $|X|\le \tfrac{2n-6}{g}$ if $g\ge 6$. This improves recent results of Golowich and Rolnick.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.