  An exact $(k,d)$-coloring of a graph $G$ is a coloring of its vertices with
$k$ colors such that each vertex $v$ is adjacent to exactly $d$ vertices having
the same color as $v$. The exact $d$-defective chromatic number, denoted
$\chi_d^=(G)$, is the minimum $k$ such that there exists an exact
$(k,d)$-coloring of $G$. In an exact $(k,d)$-coloring, which for $d=0$
corresponds to a proper coloring, each color class induces a $d$-regular
subgraph. We give basic properties for the parameter and determine its exact
value for cycles, trees, and complete graphs. In addition, we establish bounds
on $\chi_d^=(G)$ for all relevant values of $d$ when $G$ is planar, chordal, or
has bounded treewidth. We also give polynomial-time algorithms for finding
certain types of exact $(k,d)$-colorings in cactus graphs and block graphs. Our
main result is on the computational complexity of $d$-EXACT DEFECTIVE
$k$-COLORING in which we are given a graph $G$ and asked to decide whether
$\chi_d^=(G) \leq k$. Specifically, we prove that the problem is NP-complete
for all $d \geq 1$ and $k \geq 2$.
