Domatic number

In graph theory, a domatic partition of a graph G = ( V , E ) {displaystyle G=(V,E)} is a partition of V {displaystyle V} into disjoint sets V 1 {displaystyle V_{1}} , V 2 {displaystyle V_{2}} ,..., V K {displaystyle V_{K}} such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set V 1 {displaystyle V_{1}} consists of the yellow vertices, V 2 {displaystyle V_{2}} consists of the green vertices, and V 3 {displaystyle V_{3}} consists of the blue vertices. In graph theory, a domatic partition of a graph G = ( V , E ) {displaystyle G=(V,E)} is a partition of V {displaystyle V} into disjoint sets V 1 {displaystyle V_{1}} , V 2 {displaystyle V_{2}} ,..., V K {displaystyle V_{K}} such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set V 1 {displaystyle V_{1}} consists of the yellow vertices, V 2 {displaystyle V_{2}} consists of the green vertices, and V 3 {displaystyle V_{3}} consists of the blue vertices. The domatic number is the maximum size of a domatic partition, that is, the maximum number of disjoint dominating sets. The graph in the figure has domatic number 3. It is easy to see that the domatic number is at least 3 because we have presented a domatic partition of size 3. To see that the domatic number is at most 3, we first review a simple upper bound. Let δ {displaystyle delta } be the minimum degree of the graph G {displaystyle G} . The domatic number of G {displaystyle G} is at most δ + 1 {displaystyle delta +1} . To see this, consider a vertex v {displaystyle v} of degree δ {displaystyle delta } . Let N {displaystyle N} consist of v {displaystyle v} and its neighbours. We know that (1) each dominating set V i {displaystyle V_{i}} must contain at least one vertex in N {displaystyle N} (domination), and (2) each vertex in N {displaystyle N} is contained in at most one dominating set V i {displaystyle V_{i}} (disjointness). Therefore there are at most | N | = δ + 1 {displaystyle |N|=delta +1} disjoint dominating sets. The graph in the figure has minimum degree δ = 2 {displaystyle 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. If there is no isolated vertex in the graph (that is, δ {displaystyle 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. Finding a domatic partition of size 1 is trivial: let V 1 = V {displaystyle 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 {displaystyle G} and an integer K {displaystyle K} , determine whether the domatic number of G {displaystyle G} is at least K {displaystyle 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 | ) {displaystyle O(log |V|)} of the optimum.