Approximation algorithm for minimum q-dominator partization problem

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χd(G). Graphs with χd(G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4, deciding whether χd(G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q-dominator partization problem (Min-q-D-Partz). In Min-q-D-Partz, given a graph G, the objective is to find a vertex set S of minimum size such that χd(G[V â S]) ≤ q. We prove that Min-2-D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min-3-D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O(log n).