Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph

Abstract

The maximum average degree $\mathrm{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 $\mathrm{mad}(G)\ge k$ there exists $S\subseteq V(G)$ such that $\mathrm{mad}(G-S)\le \mathrm{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 $\mathrm{mad}(G-I)\le \mathrm{mad}(G)-1$ and an induced forest $F$ such that $\mathrm{mad}(G-F)\le \mathrm{mad}(G)-2$.