Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph (Q2121792)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph |
scientific article |
Statements
Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph (English)
0 references
4 April 2022
0 references
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}\).
0 references
sparse graph classes
0 references
reconfiguration graphs
0 references
0 references
0 references
0 references