Domatic partitions and the Lovász local lemma (Q2768400)

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called domainting in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). A partition of \(G\), all of whose classes are dominating sets in \(G\), is called a domatic partition of \(G\). The maximum number of classes of a domatic partition of \(G\) is the domatic number \(D(G)\) of \(G\). The author's main result reads: There is a constant \(a>0\) such that for any graph \(G\) with minimu degree \(\delta= \delta(G)\) and maximum degree \(\Delta= \Delta(G) \geq 3\), we have \(D(G)\geq\delta/ (\ln \Delta+a\ln\ln\Delta)\). Only a sketch of proof is presented, because this paper is only the text of a lecture at a symposium. The complete proof will appear in a quoted reference.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].