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

About 10 years old · traced to

Let n≥3n\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.

References

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.

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.