Decomposing the Complete Graph into Forests

276 Views Asked by At

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility conditions we need on $n$ (in particular if $F$ is the forest, the sum of its degrees divides $n(n-1)$). The two examples I know of for $n$ even are perfect matchings and hamiltonian paths. Can we classify the forests that will work?
(edit) Clarification: By a partition of $K_n$ I am talking about a partition of the edge set of $K_n$, all $n \choose 2$ edges, into copies of the forest $F$.

1

There are 1 best solutions below

2
On

The problem you pose seems to be wide open, as indicated in a number of recent publications devoted to it. Even in a special case when a forest is a tree not as much is known. There is a recent conjecture by Haler and Wang: $k$ edge disjoint copies of a tree $T$ on $n$ vertices can be placed in the complete graph if and only if every vertex of $T$ has degree less than $n-k$, see their paper (checking it for $k=4$) for precise formulation.

When $F$ is an arbitrary forest, less seems to be known. There are interesting results concerning arbitrary graphs $F$, as well as those on many other graph classes, though.