Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes

A k vertex coloring of a graph G = (V, E) partitions the vertex set into k color classes (or independent sets). In minimum vertex coloring problem, the aim is to minimize the number of colors used in a given graph. Here, we consider three variations of vertex coloring problem in which (i) each vertex in G dominates a color class, (ii) each color class is dominated by a vertex and (iii) each vertex is dominating a color class and each color class is dominated by a vertex. These minimization problems are known as Min-Dominator-Coloring, Min-CD-Coloring and Min-Domination-Coloring, respectively. In this paper, we present approximation hardness results for these problems for some restricted class of graphs.