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

Wojciech Nadara¹ ; Marcin Smulewicz¹

¹University of Warsaw

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

The maximum average degree $\mathrm{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 $\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, if $G$ contains at least one edge then there exists an independent set $I$ in $G$ such that $\mathrm{mad}(G-I) \le \mathrm{mad}(G)-1$ and if $G$ contains a~cycle then there exists an induced forest $F$ such that $\mathrm{mad}(G-F) \le \mathrm{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 $\mathrm{mad}$.

Détail

DOI : 10.37236/9455

Classification : 05C07, 05C35, 05C10, 05C15, 05C20, 05C21, 05C69, 05C75
Mots-clés : sparse graph classes, reconfiguration graphs