MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Finding maximal k-degenerate subgraphs

Given a graph $G$, let $H$ be a $k$-degenerate (not necessarily induced) subgraph of maximal size. Are there any known lower bounds on $|E(H)|$ for particular classes of $G$ and values of $k$?

I've seen several papers on the subject, but only for induced subgraphs $H$. I'm particularly interested in the case where $k=2$ and $G$ is both regular and bipartite, but any additional information would be helpful.

(I'm aware of the naive lower bound found by arbitrarily removing edges until no vertex has degree $(k+1)$ or more...I'm looking for something better).

-
 what does $k$-degenerate means? – Dima Pasechnik Sep 24 at 7:03 @Dima - $k$-degenerate means that every subgraph has a vertex of degree at most $k$. Equivalently, repeatedly remove the vertex of minimum degree until the graph is gone; the degeneracy number of the graph is the biggest degree you saw along the way. – gordon-royle Sep 24 at 22:47