Pach–Saghafian–Schnider lower-bound conjecture for plane star-forest decompositions

About 2 years old · traced to

A complete geometric graph is a complete graph drawn with vertices in general position and straight-line edges. A plane kk-star-forest is a star-forest with at most kk connected components. Pach–Saghafian–Schnider's conjecture. The number of plane kk-star-forests needed to decompose a complete geometric graph on nn vertices is at least

(k+1)n2k.\frac{(k+1)n}{2k}.

This conjecture concerns the variant in which each star-forest is required to have at most kk components; the source gives no resolution, so the lower bound remains open.

References

Primary source

Todor Antić, Jelena Glišić and Milan Milivojčević, “Star-Forest Decompositions of Complete Graphs”, arXiv:2402.11044 (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.