Exact induced-degenerate-subgraph ratio conjecture for k-degenerate graphs
Exact induced-degenerate-subgraph ratio conjecture for k-degenerate graphs
Let denote the infimum, over -degenerate graphs, of the ratio of the order of a largest induced -degenerate subgraph to the number of vertices. Induced-degenerate-subgraph ratio conjecture for . For all integers and with ,
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
Sign in to submit a solution.
No solutions have been posted yet.