  Domination and coloring are two classic problems in graph theory. The major
focus of this paper is the CD-COLORING problem which combines the flavours of
domination and colouring. Let $G$ be an undirected graph. A proper vertex
coloring of $G$ is a $cd-coloring$ if each color class has a dominating vertex
in $G$. The minimum integer $k$ for which there exists a $cd-coloring$ of $G$
using $k$ colors is called the cd-chromatic number, $\chi_{cd}(G)$. A set
$S\subseteq V(G)$ is a total dominating set if any vertex in $G$ has a neighbor
in $S$. The total domination number, $\gamma_t(G)$ of $G$ is the minimum
integer $k$ such that $G$ has a total dominating set of size $k$. A set
$S\subseteq V(G)$ is a $separated-cluster$ if no two vertices in $S$ lie at a
distance 2 in $G$. The separated-cluster number, $\omega_s(G)$, of $G$ is the
maximum integer $k$ such that $G$ has a separated-cluster of size $k$.
  In this paper, first we explore the connection between CD-COLORING and TOTAL
DOMINATION. We prove that CD-COLORING and TOTAL DOMINATION are NP-Complete on
triangle-free $d$-regular graphs for each fixed integer $d\geq 3$. We also
study the relationship between the parameters $\chi_{cd}(G)$ and $\omega_s(G)$.
Analogous to the well-known notion of `perfectness', here we introduce the
notion of `cd-perfectness'. We prove a sufficient condition for a graph $G$ to
be cd-perfect (i.e. $\chi_{cd}(H)= \omega_s(H)$, for any induced subgraph $H$
of $G$) which is also necessary for certain graph classes (like triangle-free
graphs). Here, we propose a generalized framework via which we obtain several
exciting consequences in the algorithmic complexities of special graph classes.
In addition, we settle an open problem by showing that the SEPARATED-CLUSTER is
polynomially solvable for interval graphs.
