Star-Forest Decompositions of Complete (Geometric) Graphs

A star-forest is a forest in which every component is a star. A plane star-forest is a star-forest drawn in the plane with no crossings. We deal with the problem of decomposing Complete (Geometric) Graphs into (plane) star-forests. In the Abstract case, it is known that $K_n$ can be decomposed into $\lceil \frac{n}{2}\rceil+1 $ star-forests and that this is is thight. We show that for even $n$, any such forest is "unique" in a certain sense. We also construct Complete Geometric Graphs on $n$ vertices which can be decomposed into $\lceil \frac{n}{2}\rceil +1$ plane star-forests, resolving the conjecture of Pach, Saghafian and Schnider.

This is joint work with Milan Milivojčević and Jelena Glišić