Half-induced-forest conjecture for graphs on surfaces

For a graph GG with nn vertices and genus gg, let α1(G)\alpha_1(G) denote the order of a largest induced 11-degenerate subgraph of GG, equivalently a largest induced forest. Half-induced-forest conjecture. For every non-negative integer gg, there exists a constant f(g)f(g) such that every graph GG of genus gg satisfies

α1(G)n2f(g).\alpha_1(G)\geq \frac{n}{2}-f(g).

The conjecture is known for triangle-free planar graphs, where the source cites the stronger bound α1(G)(6n+7)/11\alpha_1(G)\geq (6n+7)/11. 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

Never refreshed

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

Solutions 0

No solutions have been posted yet.