On a Graph Partition Result of Kihn and Osthus

Abstract

Kühn and Osthus $[2]$ proved that for every positive integer $\ell$, there exists an integer $k(\ell )\le 2^{11}.3{\ell }^2$, such that the vertex set of every graph $G$ with $\delta (G)\ge k(\ell )$ can be partitioned into subsets $S$ and $T$ with the properties that $\delta (G[S])\ge \ell \le \delta (G[T])$ and every vertex of $S$ has at least $\ell$ neighbors in $T$. In this note, we improve the upper bound to $k(\ell )\le 2^4–17{\ell }^2$.