Integer and fractional packing of families of graphs
| dc.creator | Yuster, Raphael | |
| dc.date | 2003-05-25 | |
| dc.date | 2003-07-27 | |
| dc.date.accessioned | 2026-07-07T04:58:15Z | |
| dc.date.available | 2026-07-07T04:58:15Z | |
| dc.description | Let ${\cal F}$ be a family of graphs. For a graph $G$, the {\em ${\cal F}$-packing number}, denoted $ν_{\cal F}(G)$, is the maximum number of pairwise edge-disjoint elements of ${\cal F}$ in $G$. A function $ψ$ from the set of elements of ${\cal F}$ in $G$ to $[0,1]$ is a {\em fractional ${\cal F}$-packing} of $G$ if $\sum_{e \in H \in {\cal F}} {ψ(H)} \leq 1$ for each $e \in E(G)$. The {\em fractional ${\cal F}$-packing number}, denoted $ν^*_{\cal F}(G)$, is defined to be the maximum value of $\sum_{H \in {{G} \choose {\cal F}}} ψ(H)$ over all fractional ${\cal F}$-packings $ψ$. Our main result is that $ν^*_{\cal F}(G)-ν_{\cal F}(G) = o(|V(G)|^2)$. Furthermore, a set of $ν_{\cal F}(G) -o(|V(G)|^2)$ edge-disjoint elements of ${\cal F}$ in $G$ can be found in randomized polynomial time. For the special case ${\cal F}=\{H_0\}$ we obtain a significantly simpler proof of a recent difficult result of Haxell and Rödl \cite{HaRo} that $ν^*_{H_0}(G)-ν_{H_0}(G) = o(|V(G)|^2)$. | |
| dc.description | 8 pages | |
| dc.identifier | https://arxiv.org/abs/math/0305350 | |
| dc.identifier | http://arxiv.org/abs/math/0305350 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67563 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C70 | |
| dc.title | Integer and fractional packing of families of graphs | |
| dc.type | text |