The k-partition problem is as follows: Given a graph G and a positive integer k, partition the vertices of G into at most k parts $A_1, A_2, \ldots , A_k$, where it may be specified that $A_i$ induces a stable set, a clique, or an arbitrary subgraph, and pairs $A_i, A_j (i \neq j)$ be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list k-partition problem generalizes the k-partition problem by specifying for each vertex x, a list $L(x)$ of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list k-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem 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.

Abstract For any directed graph G with node‐set V(G), we present an O([V(G)]3) algorithm that finds a partition P of V(G) into directed paths and an independent set I of nodes, such that |P=|I| The existence of such a P and I is the Gallai‐Milgrm theorem. Where G is transitive and acyclic, the well‐known Dilworth theorem that min |P| = max |I| follows immediately. Where G is bipartitite and every edge of G is directed from node‐set U to node‐set V, P corresponds to a largest matching in G.