Half-induced-forest conjecture for graphs on surfaces
Half-induced-forest conjecture for graphs on surfaces
For a graph with vertices and genus , let denote the order of a largest induced -degenerate subgraph of , equivalently a largest induced forest. Half-induced-forest conjecture. For every non-negative integer , there exists a constant such that every graph of genus satisfies
The conjecture is known for triangle-free planar graphs, where the source cites the stronger bound . It remains open for graphs on surfaces in general.
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).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.