Integer and fractional packings in dense graphs

Citation
Pe. Haxell et V. Rodl, Integer and fractional packings in dense graphs, COMBINATORI, 21(1), 2001, pp. 13-38
Citations number
13
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
21
Issue
1
Year of publication
2001
Pages
13 - 38
Database
ISI
SICI code
0209-9683(2001)21:1<13:IAFPID>2.0.ZU;2-E
Abstract
Let H-0 be any fixed graph. For a graph G we define nu (H0)(G) to be the ma ximum size of a set of pairwise edge-disjoint copies of H-0 in G. We say a function psi from the set of copies of H-0 in G to [0, 1] is a, fractional H-0-packing of G if Sigma (He)psi (H)less than or equal to1 for every edge e of G. Then nu (H0)* (G) is defined to be the maximum value of Sigma (H is an element of)((G)(H0)) psi (H) over all fractional H-0-packings psi of G. We show that nu (H0)* (G)-nu (H0) (G) = o(\V(G)\(2)) for all graphs G.