Polynomial degeneracy conjecture for graphs excluding subdivisions

For a graph HH, call a graph GG HH-subdivision-free if it has no subdivision of HH as an induced subgraph. Let K,K_{\ell,\ell} denote the complete bipartite graph with \ell vertices in each part, and let the degeneracy of GG be the least integer dd such that every induced subgraph of GG has a vertex of degree at most dd.

Polynomial degeneracy conjecture for graphs excluding subdivisions. For every graph HH, every HH-subdivision-free graph GG that does not contain K,K_{\ell,\ell} as a subgraph has degeneracy at most f(H,)f(H,\ell), where ff depends polynomially on \ell.

The analogous assertion for forbidden induced trees is known, with a bound polynomial in \ell, whereas the proposed extension to arbitrary graphs HH remains open.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé and Bartosz Walczak, “Degeneracy of P_t-free and C_t-free graphs with no large complete bipartite subgraphs”, arXiv:2012.03686 (2021).

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.