List partition problem for graphs Prof. R. Sritharan University of Dayton, U.S.A. 250803 Abstract Suppose we are given graph G and a symmetric k by k matrix M over {0, 1, *}. We can attempt to partition the vertexset of G into at most k parts, A1, A2, ..., Ak, subject to the restrictions specified by M interpreted as follows: if M[i,j] = 1 (or 0), then we desire all (or no) edges between vertices placed in Ai and vertices placed in Aj. If M[i,j] = *, then we do not care about adjacencies between vertices in Ai and vertices in Aj. A diagonal entry M[i,i] = 1 (0, or *) specifies that the subgraph induced by Ai be a complete graph (an independent set, or an arbitrary subgraph). The "Mpartition problem" asks "Given G and a symmetric k by k matrix M over {0, 1, *}, does G admit a partition subject to M ?". Several well known graph theoretic problems (such as "Is G kcolourable ?", "Does G have a cliquecutset ?") are special cases of the partition problem formulated as above. In an instance of the "list Mpartition problem", in addition to being given graph G and a symmetric k by k matrix M as above, for each vertex v of G we are given a list L(v) which is a subset of {A1, A2, ..., Ak}. The problem asks "Is there a partition of G subject to M in which each vertex v is assigned to a part in L(v) ?". List Mpartition problem is a generalization of listcoloring as well as listhomomorphism problems. Feder, Hell, Klein, and Motwani (STOC 99) proved that, when k=4, every such list Mpartition problem is either solvable in quasipolynomial time or NPcomplete. We prove that for the case k=4, with the exception of one specific problem, every list Mpartition problem is either solvable in polynomial time or NPcomplete. In proving this, we also show polynomial time solvability of some specific problems whose status was open.
