Domatic number

Let \delta be the minimum degree of the graph G. The domatic number of G is at most \delta + 1. To see this, consider a vertex v of degree \delta. Let N consist of v and its neighbours. We know that (1) each dominating set V_i must contain at least one vertex in N (domination), and (2) each vertex in N is contained in at most one dominating set V_i (disjointness). Therefore, there are at most |N| = \delta + 1 disjoint dominating sets. The graph in the figure has minimum degree \delta = 2, and therefore its domatic number is at most 3. Hence we have shown that its domatic number is exactly 3; the figure shows a maximum-size domatic partition. ==Lower bounds==

If there is no isolated vertex in the graph (that is, \delta ≥ 1), then the domatic number is at least 2. To see this, note that (1) a weak 2-coloring is a domatic partition if there is no isolated vertex, and (2) any graph has a weak 2-coloring. Alternatively, (1) a maximal independent set is a dominating set, and (2) the complement of a maximal independent set is also a dominating set if there are no isolated vertices. The figure on the right shows a weak 2-coloring, which is also a domatic partition of size 2: the dark nodes are a dominating set, and the light nodes are another dominating set (the light nodes form a maximal independent set). See weak coloring for more information. ==Computational complexity==

Finding a domatic partition of size 1 is trivial: let V_1 = V. Finding a domatic partition of size 2 (or determining that it does not exist) is easy: check if there are isolated nodes, and if not, find a weak 2-coloring. However, finding a maximum-size domatic partition is computationally hard. Specifically, the following decision problem, known as the domatic number problem, is NP-complete: given a graph G and an integer K, determine whether the domatic number of G is at least K. Therefore, the problem of determining the domatic number of a given graph is NP-hard, and the problem of finding a maximum-size domatic partition is NP-hard as well. There is a polynomial-time approximation algorithm with a logarithmic approximation guarantee, that is, it is possible to find a domatic partition whose size is within a factor O(\log |V|) of the optimum. However, under plausible complexity-theoretic assumptions, there is no polynomial-time approximation algorithm with a sub-logarithmic approximation factor. More specifically, a polynomial-time approximation algorithm for domatic partition with the approximation factor (1-\epsilon) \ln |V| for a constant \epsilon > 0 would imply that all problems in NP can be solved in slightly super-polynomial time n^{O(\log \log n)}. ==Comparison with similar concepts==

; Domatic partition : Partition of vertices into disjoint dominating sets. The domatic number is the maximum number of such sets. ; Vertex coloring : Partition of vertices into disjoint independent sets. The chromatic number is the minimum number of such sets. ; Clique partition : Partition of vertices into disjoint cliques. Equal to vertex coloring in the complement graph. ; Edge coloring : Partition of edges into disjoint matchings. The edge chromatic number is the minimum number of such sets. Let G = (U ∪ V, E) be a bipartite graph without isolated nodes; all edges are of the form {u, v} ∈ E with u ∈ U and v ∈ V. Then {U, V} is both a vertex 2-coloring and a domatic partition of size 2; the sets U and V are independent dominating sets. The chromatic number of G is exactly 2; there is no vertex 1-coloring. The domatic number of G is at least 2. It is possible that there is a larger domatic partition; for example, the complete bipartite graph Kn,n for any n ≥ 2 has domatic number n. ==Notes==