The partial saturation ratio bound for planar graphs with bounded twin multiplicities

Let k1,k2k_1,k_2 be non-negative integers, let Gk1,k2\mathcal{G}_{k_1,k_2} be the class of graphs under consideration, and let GGk1,k2G\in\mathcal{G}_{k_1,k_2}. Write psr(G)\operatorname{psr}(G) for the partial saturation ratio.

Partial saturation ratio conjecture. Every such graph satisfies

psr(G)>19+k1+6k2.\operatorname{psr}(G)>\frac{1}{9+k_1+6k_2}.

The paper states that this is the best possible bound, based on a construction, and notes that the case k1=k2=0k_1=k_2=0 is of greatest interest. The conjecture extends the theorem proved for some pairs of non-negative integers to all such pairs.

Sources & referencesView supporting material

Primary source

Alexander Clifton and Nika Salia, “Saturated Partial Embeddings of Planar Graphs”, arXiv:2403.02458 (2024).

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.