Sparse-host induced subdivision extremal conjecture
Sparse-host induced subdivision extremal conjecture
Let be a graph, and let be the property of not containing a subdivision of as an induced subgraph. For a graph , write for the maximum number of edges in a subgraph of with this property. For , say that is -sparse when it satisfies the sparsity condition used in the paper. Sparse-host induced subdivision extremal conjecture. For every and a graph , there exists such that, if is a -sparse graph, then
The motivation is a result showing that sufficiently dense graphs with no contain an induced subdivision of ; the stated sparse-host extremal estimate remains open.
Sources & referencesView supporting material
Primary source
Jacob Fox, Rajko Nenadov and Huy Tuan Pham, “The largest subgraph without a forbidden induced subgraph”, arXiv:2405.05902 (2024).
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.