On the complexity of minimum q-domination partization problems

A domination coloring of a graph G is a proper vertex coloring with an additional condition that each vertex dominates a color class and each color class is dominated by a vertex. The minimum number of colors used in a domination coloring of G is denoted as chi(dd)(G) and it is called domination chromatic number of G. In this paper, we give a polynomial-time characterization of graphs with domination chromatic number at most 3 and consider the approximability of a node deletion problem called minimum q-domination partization. Given a graph G, in the Minimumq-Domination Partization problem (in short Min-q-Domination-Partization), the objective is to find a vertex set S of minimum size such that chi(dd)(G[V\S]) <= q. For q = 2, we prove that it is APX-complete and is best approximable within a factor of 2. For q = 3, it is approximable within a factor of O(root log n) and it is equivalent to minimum odd cycle transversal problem.