04112614

j

04112614 Lonc, Zbigniew Decompositions of graphs into trees. J. Graph Theory 13, No.4, 393-403 (1989). 1989 John Wiley \& Sons, New York, NY EN theta-decomposition edge partition

doi:10.1002/jgt.3190130403

Let $\theta$ be a family of graphs. A $\theta$-decomposition of a graph G is a partition $\pi$ of the edge set of G such that every $F\in \pi$ induces in G a subgraph isomorphic to a graph in $\theta$. Denote by $<\theta >$ the set of all graphs that have a $\theta$ decomposition. Several authors have proved that for some special families of graphs $\theta$, if the graph G is large enough and satisfies some obvious necessary conditions, then $G\in <\theta >$. In this paper the focus is on graphs with large degree. In particular, the following conjecture is proved for certain pairs of trees: If $T\sb 1$ and $T\sb 2$ are two trees having relatively prime sizes then there exists $c=c(T\sb 1,T\sb 2)$ such that every graph G satisfying the condition $\delta$ (G)$\ge c$ belongs to $<\{T\sb 1,T\sb 2\}>$. The proof rests on the author's proof of a packing theorem for rooted trees of given diameter and maximum degree. R.C.Entringer