Conjecture on collecting all but one twelfth of a planar graph
Conjecture on collecting all but one twelfth of a planar graph
Let 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 ; a set is collectable if its vertices can be collected in some sequence. Collecting conjecture. One can delete at most of the vertices of so that all remaining vertices can be collected. The collected vertices consequently induce a -degenerate subgraph. The preceding results guarantee deletion of less than of the vertices, while the icosahedron shows that one deleted vertex may be necessary; the source presents the stronger 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
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.