Kathie Cameron
ABSTRACT
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.
Recommendations
The Complexity of the List Partition Problem for Graphs
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 ...
Adapted list coloring of planar graphs
Given an edge coloring F of a graph G, a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |...
An extremal problem for vertex partition of complete multipartite graphs
For a graph G and a family H of graphs, a vertex partition of G is called an H -decomposition, if every part induces a graph isomorphic to one of H . For 1 a k , let A ( k , a ) denote the graph which is a join of an empty graph of order a and a ...
Comments