Lower-bound conjecture for plane star-forest decompositions of complete geometric graphs

From papers

A complete geometric graph is a complete graph drawn with vertices in general position and straight-line edges. A plane star-forest is a forest whose connected components are stars. Star-forest decomposition lower-bound conjecture. Let n1n\ge1. There is no complete geometric graph with nn vertices that can be decomposed into fewer than

3n4\left\lceil\frac{3n}{4}\right\rceil

plane star-forests. The source presents this as a conjecture based on the lower bound known for vertices in convex position; its general case remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Todor Antić, Jelena Glišić and Milan Milivojčević, “Star-Forest Decompositions of Complete Graphs”, arXiv:2402.11044 (2024).

Solutions 0

No solutions have been posted yet.