Partitioning graphs into generalized dominating sets
Pinar Heggernes, Jan Arne Telle · 1998
. We study the computational complexity of partitioning the vertices of a graph into generalized dominating sets. Generalized dominating sets are parameterized by two sets of nonnegative integers oe and ae which constrain the neighborhood N(v) of vertices. A set S of vertices of a graph is said to be a (oe; ae)-set if 8v 2 S : jN(v) " Sj 2 oe and 8v 62 S : jN(v) " Sj 2 ae. The (k; oe; ae)-partition problem asks for the existence of a partition V 1 ; V 2 ; :::; V k of vertices of a given graph G such that V i ; i = 1; 2; :::; k is a (oe; ae)-set of G. We study the computational complexity of this problem as the parameters oe; ae and k vary. 1. Motivation and overview Several well-studied graph problems ask for a partition of vertices of a graph into subsets with a given property. For example, the Chromatic Number problem asks for a partition into the least number of independent sets. Even the fixed parameter version of this problem, vertex k-coloring, where we ask for the existence o...