The Domatic Number of Regular and Almost Regular Graphs

The domatic number of a graph denoted (), is the maximum possible cardinality of a family of disjoint sets of vertices of each set being a dominating set of It is well known that every graph without isolated vertices has () ≥ 2. For every it is known that there are graphs with minimum degree at least and with () = 2. In this paper we prove that this is not the case if is -regular or -regular (by “almost” we mean that the minimum degree is and the maximum degree is at most for some fixed real number ≥ 1). In this case we prove that () ≥ (1 + (1))/(2 ln ). We also prove that the order of magnitude /ln cannot be improved. One cannot replace the constant 2 with a constant smaller than 1. The proof uses the so called which means that combinatorial objects are generated via repeated applications of the probabilistic method; in our case iterative applications of the Lovász Local Lemma