Domatic number

Upper bounds

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

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,{{citation

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 K**n,n for any n ≥ 2 has domatic number n.

Notes

References

• . A1.1: GT3, p. 190.
• {{citation