Induced forest bound for graphs of prescribed girth
Induced forest bound for graphs of prescribed girth
Let be a graph on vertices with edges, and let denote the order of a largest induced -degenerate subgraph of , equivalently a largest induced forest. Induced forest girth conjecture. For every integer , if has girth at least , then
The source notes that the bound would be best possible, as witnessed by a disjoint union of cycles of length , and that the case of girth 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
Sign in to submit a solution.
No solutions have been posted yet.