Integer and fractional packing of families of graphs

Details Integer and fractional packing of families of graphs Integer and fractional packing of families of graphs

2003-05-25

arxiv.org/abs/math/0305350v4

Mathematics

Combinatorics

8 pages

Scientific paper

Let ${\cal F}$ be a family of graphs. For a graph $G$, the {\em ${\cal F}$-packing number}, denoted $\nu_{{\cal F}}(G)$, is the maximum number of pairwise edge-disjoint elements of ${\cal F}$ in $G$. A function $\psi$ 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}} {\psi(H)} \leq 1$ for each $e \in E(G)$. The {\em fractional ${\cal F}$-packing number}, denoted $\nu^*_{{\cal F}}(G)$, is defined to be the maximum value of $\sum_{H \in {{G} \choose {{\cal F}}}} \psi(H)$ over all fractional ${\cal F}$-packings $\psi$. Our main result is that $\nu^*_{{\cal F}}(G)-\nu_{{\cal F}}(G) = o(|V(G)|^2)$. Furthermore, a set of $\nu_{{\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\"odl \cite{HaRo} that $\nu^*_{H_0}(G)-\nu_{H_0}(G) = o(|V(G)|^2)$.

Affiliated with

Also associated with

No associations

Rating

Integer and fractional packing of families of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Integer and fractional packing of families of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integer and fractional packing of families of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-713827