A Note on Large Degenerate Induced Subgraphs in Sparse Graphs

Abstract

Given a graph $G$ and a non-negative integer $d$ let $\hat{I}{\pm }_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 $\hat{I}{\pm }_d(G)\ge \max \{\frac{(d+1)n}{k+d+1},n-\hat{I}{\pm }_{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 $\hat{I}{\pm }_d(G)$ for graphs of bounded genus. This extends earlier work on degenerate subgraphs of planar graphs.

9 pages