Conjectured sharp upper bounds for induced degenerate subgraphs of planar graphs
Let denote the minimum, over planar graphs, of the maximum order of a -degenerate induced subgraph divided by the number of vertices. The octahedron and icosahedron give upper bounds for the cases . The sharp-bound conjecture.
The source proves the lower bound corresponding to only at , while the displayed values are witnessed as upper bounds by the cited extremal planar graphs; the conjecture remains open according to the supplied status evidence.
References
Primary source
Y. Gu, H. A. Kierstead, Sang-il Oum, Hao Qi and Xuding Zhu, “3-degenerate induced subgraph of a planar graph”, arXiv:2002.07984 (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
No solutions have been posted yet.