Polynomial degeneracy conjecture for graphs excluding subdivisions

At least 5 years old · documented by

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.

References

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.