Conjectured sharp upper bounds for induced degenerate subgraphs of planar graphs

Let αˉd\bar\alpha_d denote the minimum, over planar graphs, of the maximum order of a dd-degenerate induced subgraph divided by the number of vertices. The octahedron and icosahedron give upper bounds for the cases d=2,3,4d=2,3,4. The sharp-bound conjecture.

αˉ2=2/3,αˉ3=5/6,αˉ4=11/12.\bar\alpha_2=2/3,\qquad \bar\alpha_3=5/6,\qquad \bar\alpha_4=11/12.

The source proves the lower bound corresponding to d=3d=3 only at 3/43/4, 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

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.