Domatic number

In graph theory, a domatic partition of a graph ${\displaystyle G=(V,E)}$ is a partition of ${\displaystyle V}$ into disjoint sets ${\displaystyle V_{1}}$, ${\displaystyle V_{2}}$,...,${\displaystyle V_{K}}$ such that each V_i is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set ${\displaystyle V_{1}}$ consists of the yellow vertices, ${\displaystyle V_{2}}$ consists of the green vertices, and ${\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.