Edge-disjoint induced subgraphs with given minimum degree (Q1953440)

Summary: 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 \textit{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 \geq 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.