Asymptotic maximal plane-saturation ratio conjecture
Asymptotic maximal plane-saturation ratio conjecture
For a maximal planar graph on vertices, let its plane-saturation ratio be the relevant ratio measuring the size of a largest plane-saturated subgraph relative to . Plane-saturation ratio conjecture. If tends to infinity, the maximum value of the plane-saturation ratio over the set of maximal planar graphs on vertices tends to
The paper establishes a lower bound for this maximum but states that asymptotic optimality of the lower bound is only suspected, so the limiting value remains open.
Sources & referencesView supporting material
Primary source
Alexander Clifton and Dániel G. Simon, “Saturated Partial Embeddings of Maximal Planar Graphs”, arXiv:2412.06068 (2024).
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.