×

Integer and fractional packings in dense graphs. (English) Zbl 1107.05304

Summary: Let \(H_0\) be any fixed graph. For a graph \(G\) we define \(\nu_{H_0}(G)\) to be the maximum size of a set of pairwise edge-disjoint copies of \(H_0\) in \(G\). We say a function \(y\) from the set of copies of \(H_0\) in \(G\) to \([0, 1]\) is a fractional \(H_0\)-packing of \(G\) if \(\sum_{H\ni e}\psi (H)\leq 1\) for every edge \(e\) of \(G\). Then \(\nu_{H_0}^*(G)\) is defined to be the maximum value of \(\sum_{H\in \binom{G}{H_0}} \psi(H)\) over all fractional \(H_0\)-packings \(y\) of \(G\). We show that \(\nu_{H_0}^*(G)-\nu_{H_0}(G)=o(| V(G)| ^2)\) for all graphs \(G\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

packing; dense graph
Full Text: DOI