Exact induced-degenerate-subgraph ratio conjecture for k-degenerate graphs

From papers

Let αd(k)\alpha_d(k) denote the infimum, over kk-degenerate graphs, of the ratio of the order of a largest induced dd-degenerate subgraph to the number of vertices. Induced-degenerate-subgraph ratio conjecture for k3k\geq 3. For all integers k3k\geq 3 and dd with k>dk>d,

αd(k)=d+1k+1.\alpha_d(k)=\frac{d+1}{k+1}.

This assertion is motivated by computational experiments and would determine the exact ratios for the indicated parameters. The source presents it 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.