10.1184/R1/6479099.v1 Deepak Bal Deepak Bal Alan Frieze Alan Frieze Michael Krivelevich Michael Krivelevich Po-Shen Loh Po-Shen Loh Packing Tree Factors in Random and Pseudo-Random Graphs Carnegie Mellon University 2014 Tree factors Packing Random graphs Pseudo-random graphs 2014-04-01 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/Packing_Tree_Factors_in_Random_and_Pseudo-Random_Graphs/6479099 <p>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 ϵ>0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ϵ-fraction of its edges, as long as ϵ4np≫log2n. Assuming stronger divisibility conditions, the edge probability can be taken down to p>Clognn. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.</p>