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 and an integer , determine whether the domatic number of is at least . 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 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 for a constant would imply that all problems in NP can be solved in slightly super-polynomial time . 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 References . A1.1: GT3, p. 190. . Graph invariants NP-complete problems Computational problems in graph theory