Bounding the feedback vertex number of digraphs in terms of vertex degrees

DOI10.1016/j.dam.2011.01.006zbMath1222.05030arXiv1101.1291OpenAlexW2113301124MaRDI QIDQ534359

Hermann Gruber

Publication date: 17 May 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

feedback setacyclic setCaro-Wei inequalitydirected feedback vertex numberinduced DAG

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

Cites Work

• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Large induced degenerate subgraphs
• Hypergraph coverings and local colorings
• Lower bounds on the independence number in terms of the degrees
• A note on greedy algorithms for the maximum weighted independent set problem
• Turan's Graph Theorem
• On maximal transitive subtournaments
• On cliques in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item