A Note on Large Degenerate Induced Subgraphs in Sparse Graphs

Given a graph $G$ and a non-negative integer $d$ let ${\alpha }_d(G)$ be the order of a largest induced $d$-degenerate subgraph of $G$. We prove that for any pair of non-negative integers $k>d$, if $G$ is a $k$-degenerate graph, then ${\alpha }_d(G)\ge \max \{\frac{(d+1)n}{k+d+1},n-{\alpha }_{k-d-1}(G)\}$. For $k$-degenerate graphs this improves a more general lower bound of Alon, Kahn, and Seymour. By modifying our argument we obtain improved lower bound on ${\alpha }_d(G)$ for graphs of bounded genus. This extends earlier work on degenerate subgraphs of planar graphs.