We consider the problem of partitioning the vertex-set of a graph into at most  k  parts  A 1,  A 2,...,  A k,   where it may be specified that  A i   induce a stable set, a clique, or an arbitrary subgraph, and pairs  A i,  A j  (i ≠ j)  be completely non-adjacent, completely adjacent, or arbitrarily adjacent. This problem is generalized to the list version which specifies for each vertex a list of parts in which the vertex is allowed to be placed. Many well-known graph problems can be formulated as list partition problems: e.g. 3-colourability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list partition problem with  k  = 4 as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete.
['Kathie Cameron', 'Elaine M. Eschen', 'Chính T. Hoàng', 'R. Sritharan']
The list partition problem for graphs