The list partition problem for graphs
Kathie Cameron, Elaine M. Eschen, Chı́nh T. Hoàng, R. Sritharan · Symposium on Discrete Algorithms · 2004
We consider the problem of partitioning the vertex-set of a graph into at most k parts A1, A2,..., Ak, where it may be specified that Ai induce a stable set, a clique, or an arbitrary subgraph, and pairs Ai, Aj (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.