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

At least 1 year old · documented by

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 G∈Gk1,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.

References

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.