2021/11/29 by Kolja Knauer, Knauer, Kolja, Hoang La +3 · 1 citation
Computer Science · Materials Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Magnetism in coordination complexes
paper · doi:10.48550/arxiv.2111.14986
openalex publication_date 2021/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the minimum size f of a feedback vertex set in directed and undirected n-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound (k-1)/(k+1)n is known to be tight for graphs with bounded treewidth k or bounded odd degeneracy k. We show that neither of the easy upper and lower bounds (k-1)/(k+1)n and (k)/(k+2)n can be exact for the case of even degeneracy. More precisely, for even degeneracy k we prove that f < (k)/(k+2)n and for every ε>0, there exists a k-degenerate graph for which f≥ (3k-2)/(3k+4)n -ε. For directed graphs of bounded degeneracy k, we prove that f≤(k-1)/(k+1)n and that this inequality is strict when k is odd. For directed graphs of bounded treewidth k≥ 2, we show that f ≤ (k)/(k+3)n and for every ε>0, there exists a k-degenerate graph for which f≥ (k-2\lfloorlog2(k)\rfloor)/(k+1)n -ε. Further, we provide several constructions of low degeneracy or treewidth and large f.