Small Feedback Vertex Sets in Planar Digraphs

[摘要] 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

[学科分类] 离散数学和组合数学

[关键词] Planar Digraphs;Digirth;Feedback Vertex Sets