The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices in a graph, 6 the minimum degree, and A the maximum degree. Trivially, the domatic number is at most (6+ 1). We show that every graph has a domatic partition with (1-o (1))(6+ 1)/lnn sets, and moreover, that such a domatic partition can be found in polynomiM time. This implies a (1+ o (1)) lnn approximation algorithm for domatic number. We show that to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every e> 0, a (1-e) lnn-approximation implies that NP C DTIME (nlglg'~). This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better.

We also give a refined algorithm that gives a domatic partition of~ 2 (5/In A) sets. This implies an O (ln A) approximation for domatic number. We suspect that the true constant hidden by the f/notation should be 1. As a step towards confirming this, we show that every graph of girth at least five and 5 large enough has domatic number at least