Induced forest bound for graphs of prescribed girth

From papers

Let GG be a graph on nn vertices with mm edges, and let α1(G)\alpha_1(G) denote the order of a largest induced 11-degenerate subgraph of GG, equivalently a largest induced forest. Induced forest girth conjecture. For every integer k3k\geq 3, if GG has girth at least kk, then

α1(G)nmk.\alpha_1(G)\geq n-\frac{m}{k}.

The source notes that the bound would be best possible, as witnessed by a disjoint union of cycles of length kk, and that the case of girth 33 is trivial. The general assertion is presented as open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Alexander Clow, Sean Kim and Ladislav Stacho, “A Note on Large Degenerate Induced Subgraphs in Sparse Graphs”, arXiv:2511.13693 (2025).

Solutions 0

No solutions have been posted yet.