Finding the domatic number of a graph is computationally hard.

Given a complete set of minimal dominating sets, the domatic number of a graph can be found as the independence
number of the graph in which vertices are minimal dominating sets of and edges exist between pairs sets having nonempty intersection.