{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:04Z","timestamp":1753893844567,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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}$.<\/jats:p>","DOI":"10.37236\/9455","type":"journal-article","created":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T06:29:03Z","timestamp":1646980143000},"source":"Crossref","is-referenced-by-count":2,"title":["Decreasing the Maximum Average Degree by Deleting an Independent Set or a $d$-Degenerate Subgraph"],"prefix":"10.37236","volume":"29","author":[{"given":"Wojciech","family":"Nadara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Smulewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2022,3,11]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p49\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i1p49\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T06:29:04Z","timestamp":1646980144000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i1p49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,11]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.37236\/9455","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,3,11]]},"article-number":"P1.49"}}