Finding maximal k-degenerate subgraphs

Question

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).

Answer 1

Here are some very minor and mostly negative observations in the k=2 case. Obviously a 2-degenerate subgraph in an n-vertex graph can have at most 2n-3 edges. So let's ask which graphs have 2-degenerate subgraphs with exactly 2n-3 edges. Vertices of degree at most 2 can force the answer to be "no". So let's assume minimum degree at least 3. And if a graph has c components, then every 2-degenerate subgraph has at most 2n-3c edges. So let's assume that our graph is connected. But still there are graphs for which every 2-degenerate subgraph has strictly less than 2n-3 edges. Let G be a connected graph with 6 vertices of degree 3 and n-6 vertices of degree 4. (There are many ways to construct such a graph, starting from K_{3,3}.) So the total number of edges is 2n-3, but the graph itself is not 2-degenerate. So there is no 2-degenerate subgraph of G with 2n-3 edges.

I am interested in this question, so if you know something else, then please email [email protected]

Answer 2

Just a minor remark (that might be useful, who knows?)

Any $2k$-edge-connected graph on $n$ vertices contains a spanning $(2k-1)$-degenerate subgraph on $k(n-1)$ edges.

Proof: by Nash-Williams, a $2k$-edge-connected graph contains $k$ edge-disjoint spanning trees. The spanning subgraph whose edge-set consists of the union of these $k$ spanning trees is $(2k-1)$-degenerate and contains $k(n-1)$ edges.