We study the concept of an H-partition of the vertex set of a
graph G, which includes all vertex partitioning problems into
four parts which we require to be nonempty with only external
constraints according to the structure of a model graph H, with
the exception of two cases, one that has already been classified
as polynomial, and the other one remains unclassified. In the
context of more general vertex-partition problems, the problems
addressed in this paper have these properties: non-list, 4-part,
external constraints only (no internal constraints), each part
non-empty. We describe tools that yield for each problem
considered in this paper a simple and low complexity
polynomial-time algorithm.