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

Summary: The maximum average degree \(\text{mad}(G)\) of a graph \(G\) is the maximum over all subgraphs of \(G\), of the average degree of the subgraph. In this paper, we prove that for every \(G\) and positive integer \(k\) such that \(\text{mad}(G) \ge k\) there exists \(S \subseteq V(G)\) such that \(\text{mad}(G - S) \leqslant \text{mad}(G) - k\) and \(G[S]\) is \((k-1)\)-degenerate. Moreover, such \(S\) can be computed in polynomial time. In particular, if \(G\) contains at least one edge then there exists an independent set \(I\) in \(G\) such that \(\text{mad}(G-I) \le \text{mad}(G)-1\) and if \(G\) contains a cycle then there exists an induced forest \(F\) such that \(\text{mad}(G-F) \le \text{mad}(G) - 2\). As a side result, we also obtain a subexponential bound on the diameter of reconfiguration graphs of generalized colourings of graphs with bounded value of their \(\text{mad}\).