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) \leq 2^{11}.3\ell^2\), such that the vertex set of every graph \(G\) with \(\delta(G) \geq k(\ell)\) can be partitioned into subsets \(S\) and \(T\) with the properties that \(\delta(G[S]) \geq \ell \leq \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) \leq 2^4 – 17\ell^2\).