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 edge-disjoint $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 pseudo-random graphs, defined in terms of their degrees and co-degrees.
@article{10_37236_3285,
author = {Deepak Bal and Alan Frieze and Michael Krivelevich and Po-Shen Loh},
title = {Packing tree factors in random and pseudo-random graphs},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/3285},
zbl = {1300.05242},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3285/}
}
TY - JOUR
AU - Deepak Bal
AU - Alan Frieze
AU - Michael Krivelevich
AU - Po-Shen Loh
TI - Packing tree factors in random and pseudo-random graphs
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/3285/
DO - 10.37236/3285
ID - 10_37236_3285
ER -
%0 Journal Article
%A Deepak Bal
%A Alan Frieze
%A Michael Krivelevich
%A Po-Shen Loh
%T Packing tree factors in random and pseudo-random graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3285/
%R 10.37236/3285
%F 10_37236_3285
Deepak Bal; Alan Frieze; Michael Krivelevich; Po-Shen Loh. Packing tree factors in random and pseudo-random graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3285
