Edge-disjoint induced subgraphs with given minimum degree
The electronic journal of combinatorics, Tome 20 (2013) no. 1
Let $h$ be a given positive integer. For a graph with $n$ vertices and $m$ edges, what is the maximum number of pairwise edge-disjoint {\em induced} subgraphs, each having minimum degree at least $h$? There are examples for which this number is $O(m^2/n^2)$. We prove that this bound is achievable for all graphs with polynomially many edges. For all $\epsilon > 0$, if $m \ge n^{1+\epsilon}$, then there are always $\Omega(m^2/n^2)$ pairwise edge-disjoint induced subgraphs, each having minimum degree at least $h$. Furthermore, any two subgraphs intersect in an independent set of size at most $1+ O(n^3/m^2)$, which is shown to be asymptotically optimal.
@article{10_37236_2882,
author = {Raphael Yuster},
title = {Edge-disjoint induced subgraphs with given minimum degree},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2882},
zbl = {1266.05126},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2882/}
}
Raphael Yuster. Edge-disjoint induced subgraphs with given minimum degree. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2882
Cité par Sources :