Large Degenerate Subgraphs in Degenerate Graphs

Alexander Clow, Simon Fraser University

Given a graph G and a non-negative integer d let α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 αd(G) ≥ max{(d+1)n/k+d+1 , n − αk−d−1(G)}.

For k-degenerate graphs this improves a more general lower bound of Alon, Kahn, and Seymour. By modifying our arguments we also obtain an improved lower bounds on αd(G) for graphs of bounded genus. We will conclude by considering the open problem of determining αd(k) := infG with degeneracy k αd(G)/|V (G)|.

This is joint work with Sean Kim, and Ladislav Stacho.