Integer and fractional packing of families of graphs

Let F be a family of graphs. For a graph G , the F‐packing number , denoted ν F ( G ), is the maximum number of pairwise edge‐disjoint elements of F in G . A function ψ from the set of elements of F in G to [0, 1] is a fractional F‐packing of G if σ e ∈ H ∈ F ψ( H ) ≤ 1 for each e ∈ E ( G ). The fractional F‐packing number , denoted ν F * ( G ), is defined to be the maximum value of σ   H ∈(   F G )ψ( H ) over all fractional F ‐packings ψ. Our main result is that ν F * ( G )−ν F ( G ) = o (| V ( G )| 2 ). Furthermore, a set of ν F ( G )− o (| V ( G )| 2 ) edge‐disjoint elements of F in G can be found in randomized polynomial time. For the special case F = { H 0 } we obtain a simpler proof of a recent difficult result of Haxell and Rödl [Combinatorica 21 (2001), 13–38] that ν *   H   0( G ) − ν   H   0( G ) = o (| V ( G )| 2 ). Their result can be implemented in deterministic polynomial time. We also prove that the error term o (| V ( G )| 2 ) is asymptotically tight. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005