2019/09/24 by Wojciech Nadara, Nadara, Wojciech, Marcin Smulewicz +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1909.10701
openalex publication_date 2019/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The maximum average degree mad(G) of a graph G is the maximum average degree over all subgraphs of G. In this paper we prove that for every G and positive integer k such that mad(G) ≥ k there exists S ⊆ V(G) such that mad(G - S) ≤ mad(G) - k and G[S] is (k-1)-degenerate. Moreover, such S can be computed in polynomial time. In particular there exists an independent set I in G such that mad(G-I) ≤ mad(G)-1 and an induced forest F such that mad(G-F) ≤ mad(G) - 2.