Conjectured sharp upper bounds for induced degenerate subgraphs of planar graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.