# Domatic number

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Domatic_number
> Markdown URL: https://mediated.wiki/source/Domatic_number.md
> Source: https://en.wikipedia.org/wiki/Domatic_number
> Source revision: 1326501538
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Maximum number of disjoint dominating sets

A domatic partition

In [graph theory](/source/Graph_theory), a **domatic partition** of a [graph](/source/Graph_(discrete_mathematics)) G = ( V , E ) {\displaystyle G=(V,E)} is a [partition](/source/Partition_of_a_set) 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](/source/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.

## Upper bounds

Let δ {\displaystyle \delta } be the minimum [degree](/source/Degree_(graph_theory)) 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.

## Lower bounds

Weak 2-coloring

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](/source/Weak_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](/source/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](/source/Weak_coloring) for more information.

## Computational complexity

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](/source/Decision_problem), known as the **domatic number problem**, is [NP-complete](/source/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](/source/NP-hard), and the problem of finding a maximum-size domatic partition is NP-hard as well.

There is a polynomial-time [approximation algorithm](/source/Approximation_algorithm) with a logarithmic approximation guarantee,[1] 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.

However, under plausible complexity-theoretic assumptions, there is no polynomial-time approximation algorithm with a sub-logarithmic approximation factor.[1] More specifically, a polynomial-time approximation algorithm for domatic partition with the approximation factor ( 1 − ϵ ) ln ⁡ | V | {\displaystyle (1-\epsilon )\ln |V|} for a constant ϵ > 0 {\displaystyle \epsilon >0} would imply that all problems in [NP](/source/NP_(complexity)) can be solved in slightly super-polynomial time n O ( log ⁡ log ⁡ n ) {\displaystyle 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](/source/Vertex_coloring)**
- Partition of vertices into disjoint [independent sets](/source/Independent_set_(graph_theory)). The *chromatic number* is the minimum number of such sets.

**Clique partition**
- Partition of vertices into disjoint [cliques](/source/Clique_(graph_theory)). Equal to vertex coloring in the [complement graph](/source/Complement_graph).

**[Edge coloring](/source/Edge_coloring)**
- Partition of edges into disjoint [matchings](/source/Matching_(graph_theory)). The *edge chromatic number* is the minimum number of such sets.

Let *G* = (*U* ∪ *V*, *E*) be a [bipartite graph](/source/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](/source/Complete_bipartite_graph) *K**n*,*n* for any *n* ≥ 2 has domatic number *n*.

## Notes

1. ^ [***a***](#cite_ref-feige-2002_1-0) [***b***](#cite_ref-feige-2002_1-1) [Feige, Uriel](/source/Uriel_Feige); Halldórsson, Magnús M.; Kortsarz, Guy; Srinivasan, Aravind (March 2002), "Approximating the domatic number", *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*, **32** (1): 172–195, [doi](/source/Doi_(identifier)):[10.1137/S0097539700380754](https://doi.org/10.1137%2FS0097539700380754), [MR](/source/MR_(identifier)) [1954859](https://mathscinet.ams.org/mathscinet-getitem?mr=1954859)

## References

- [Garey, Michael R.](/source/Michael_Garey); [Johnson, David S.](/source/David_S._Johnson) (1979). *[Computers and Intractability: A Guide to the Theory of NP-Completeness](/source/Computers_and_Intractability)*. Series of Books in the Mathematical Sciences (1st ed.). New York: [W. H. Freeman and Company](/source/W._H._Freeman_and_Company). [ISBN](/source/ISBN_(identifier)) [9780716710455](https://en.wikipedia.org/wiki/Special:BookSources/9780716710455). [MR](/source/MR_(identifier)) [0519066](https://mathscinet.ams.org/mathscinet-getitem?mr=0519066). [OCLC](/source/OCLC_(identifier)) [247570676](https://search.worldcat.org/oclc/247570676).. A1.1: GT3, p. 190.

- Cockayne, E. J.; Hedetniemi, Stephen T. (1975), "Optimal domination in graphs", *IEEE Transactions on Circuits and Systems*, CAS-22 (11): 855–857, [doi](/source/Doi_(identifier)):[10.1109/TCS.1975.1083994](https://doi.org/10.1109%2FTCS.1975.1083994), [MR](/source/MR_(identifier)) [0384608](https://mathscinet.ams.org/mathscinet-getitem?mr=0384608).

---
Adapted from the Wikipedia article [Domatic number](https://en.wikipedia.org/wiki/Domatic_number) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Domatic_number?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.