Integer and fractional packing of families of graphs

Abstract

Let $\mathcal{F}$ be a family of graphs. For a graph $G$, the {\em $\mathcal{F}$-packing number}, denoted ${\nu }_{\mathcal{F}}(G)$, is the maximum number of pairwise edge-disjoint elements of $\mathcal{F}$ in $G$. A function $\psi$ from the set of elements of $\mathcal{F}$ in $G$ to $[0,1]$ is a {\em fractional $\mathcal{F}$-packing} of $G$ if ${\sum }_{e\in H\in \mathcal{F}}\psi (H)\le 1$ for each $e\in E(G)$. The {\em fractional $\mathcal{F}$-packing number}, denoted ${\nu }_{\mathcal{F}}^{\ast }(G)$, is defined to be the maximum value of ${\sum }_{H\in \left(\genfrac{}{}{0ex}{}{G}{\mathcal{F}}\right)}\psi (H)$ over all fractional $\mathcal{F}$-packings $\psi$. Our main result is that ${\nu }_{\mathcal{F}}^{\ast }(G)-{\nu }_{\mathcal{F}}(G)=o(|V(G){|}^2)$. Furthermore, a set of ${\nu }_{\mathcal{F}}(G)-o(|V(G){|}^2)$ edge-disjoint elements of $\mathcal{F}$ in $G$ can be found in randomized polynomial time. For the special case $\mathcal{F}=\{H_0\}$ we obtain a significantly simpler proof of a recent difficult result of Haxell and Rödl \cite{HaRo} that ${\nu }_{H_0}^{\ast }(G)-{\nu }_{H_0}(G)=o(|V(G){|}^2)$.

8 pages