#### Document Type

Article

#### Publication Date

2007

#### Department

Mathematics

#### Department

Physics & Computer Science

#### Abstract

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}*A*, where it may be specified that A

_{k}_{i}induces a stable set, a clique, or an arbitrary subgraph, and pairs

*A*,

_{i}*A*(

_{j}*i*≠

*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.

#### Recommended Citation

Cameron, Kathie; Eschen, Elaine M.; Hoàng, Chính T.; and Sritharan, R., "The Complexity of the List Partition Problem for Graphs" (2007). *Physics and Computer Science Faculty Publications*. 70.

http://scholars.wlu.ca/phys_faculty/70

## Comments

This article was originally published in

SIAM Journal on Discrete Mathematics, 21(4): 900-929. © 2007 Society for Industrial and Applied Mathematics