
Deepak Bal

Alan Frieze

Michael Krivelevich

PoShen Loh
Keywords:
Tree factors, Packing, Random graphs, Pseudorandom graphs
Abstract
For a fixed graph $H$ with $t$ vertices, an $H$factor of a graph $G$ with $n$ vertices, where $t$ divides $n$, is a collection of vertex disjoint (not necessarily induced) copies of $H$ in $G$ covering all vertices of $G$. We prove that for a fixed tree $T$ on $t$ vertices and $\epsilon>0$, the random graph $G_{n,p}$, with $n$ a multiple of $t$, with high probability contains a family of edgedisjoint $T$factors covering all but an $\epsilon$fraction of its edges, as long as $\epsilon^4 n p \gg \log^2 n$. Assuming stronger divisibility conditions, the edge probability can be taken down to $p>\frac{C\log n}{n}$. A similar packing result is proved also for pseudorandom graphs, defined in terms of their degrees and codegrees.