Convex-hull-size conjecture for optimal star-forest decompositions

From papers

Let n3n\ge3 be odd, and let GG be a complete geometric graph on nn vertices that can be decomposed into n2+1\left\lceil\frac{n}{2}\right\rceil+1 plane star-forests. Convex-hull-size conjecture. The convex hull of the vertex set V(G)V(G) has size at most

n2+1.\left\lceil\frac{n}{2}\right\rceil+1.

For even order, the source proves the analogous bound when n=2kn=2k, while the odd-order case is proposed as a conjecture. Its general validity 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).

Additional references

4 papers in this index state this conjecture (2016–2024). The statement above is taken from the most recent of them; the others are arXiv:2111.01241, arXiv:1809.10759, arXiv:1610.01676.

Solutions 0

No solutions have been posted yet.