Polynomial degeneracy conjecture for graphs excluding subdivisions
Polynomial degeneracy conjecture for graphs excluding subdivisions
For a graph , call a graph -subdivision-free if it has no subdivision of as an induced subgraph. Let denote the complete bipartite graph with vertices in each part, and let the degeneracy of be the least integer such that every induced subgraph of has a vertex of degree at most .
Polynomial degeneracy conjecture for graphs excluding subdivisions. For every graph , every -subdivision-free graph that does not contain as a subgraph has degeneracy at most , where depends polynomially on .
The analogous assertion for forbidden induced trees is known, with a bound polynomial in , whereas the proposed extension to arbitrary graphs 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
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.