Conjecture on collecting all but one twelfth of a planar graph

Let GG be a planar graph. To delete a vertex means to remove it and its incident edges. To collect a vertex means to remove it when its current degree is at most 44; a set is collectable if its vertices can be collected in some sequence. Collecting conjecture. One can delete at most 1/121/12 of the vertices of GG so that all remaining vertices can be collected. The collected vertices consequently induce a 44-degenerate subgraph. The preceding results guarantee deletion of less than 1/91/9 of the vertices, while the icosahedron shows that one deleted vertex may be necessary; the source presents the stronger 1/121/12 bound as believed optimal and gives no resolution.

Sources & referencesView supporting material

Primary source

Robert Lukoťka, Ján Mazák and Xuding Zhu, “Maximum 4-degenerate subgraph of a planar graph”, arXiv:1305.6195 (2013).

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.