Small feedback vertex sets in planar digraphs

MaRDI QIDQ528978zbMATH OpenFDO

Authors L. Esperet, Laetitia Lemoine, Frédéric Maffray

Publication date 18 May 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.04419, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p6

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

digirthfeedback vertex setsplanar digraphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Abstract: Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $gge4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|lefrac5n-59$ if $g=4$, $|X|lefrac2n-54$ if $g=5$, and $|X|lefrac2n-6g$ if $gge6$. This improves recent results of Golowich and Rolnick.

Review text

Summary: Let \(G\) be a directed planar graph on \(n\) vertices, with no directed cycle of length less than \(g\geq 4\). We prove that \(G\) contains a set \(X\) of vertices such that \(G-X\) has no directed cycle, and \(|X|\leq \tfrac{5n-5}9\) if \(g=4\), \(|X|\leq \tfrac{2n-5}4\) if \(g=5\), and \(|X|\leq \tfrac{2n-6}{g}\) if \(g\geq 6\). This improves recent results of \textit{N. Golowich} and \textit{D. Rolnick} [Electron. J. Comb. 22, No. 3, Research Paper P3.7, 9 p. (2015; Zbl 1325.05060)].

Recommendations

• Feedback vertex set on planar graphs
• On the feedback vertex set problem for a planar graph
• Connected feedback vertex set in planar graphs
• scientific article; zbMATH DE number 139781
• Feedback vertex set on graphs of low clique-width
• Feedback vertex set on graphs of low cliquewidth
• Feedback vertex set reconfiguration in planar graphs
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• Feedback vertex sets on restricted bipartite graphs
• Feedback vertex sets and cyclically reducible graphs

Cites work

• A Minimax Theorem for Directed Graphs
• Acyclic subgraphs of planar digraphs
• Planar digraphs of digirth five are 2-colorable
• Planar digraphs of digirth four are 2-colorable
• Planar digraphs without large acyclic sets

Cited in

(6)

• Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
• Acyclic subgraphs of planar digraphs
• Directed graphs without short cycles
• Planar digraphs without large acyclic sets
• Planar digraphs of digirth four are 2-colorable
• Minimum size of feedback vertex sets of planar graphs of girth at least five

This page was built for publication: Small feedback vertex sets in planar digraphs

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