Graph decompositions without isolated vertices. II (Q1389861)

The following result is proven: Let \(G\) be a connected, simple graph with \(| V(G) |= n= a_1+ a_2+ \cdots+ a_k\), \(a_i \geq 2\). Then, there is a partition of the vertices of \(G\) into \(k\) subsets, \(A_1, A_2, \ldots , A_k\) with \(| A_i |= a_i\), so that for every vertex \(v \in V(G)\) of degree at least \(k\), if \(v \in A_i\), \(v\) has degree at least one in the subgraph induced by the vertices of \(A_i\). This generalises an earlier result of \textit{H. Enomoto} [J. Comb. Theory, Ser. B 63, No. 1, 111-124 (1995; Zbl 0834.05046)] and in doing so resolves a conjecture of Y. Egawa (unpublished).