Domatically critical and domatically full graphs (Q1174128): Difference between revisions

\textit{E. J. Cockayne} [Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 141-147 (1978; Zbl 0384.05052)] proposed the study of domatically critical graphs. \textit{B. Zelinka} [Czech. Math. J. 30, 486- 489 (1980; Zbl 0426.05046)] gave a necessary condition of a graph \(G\) to be domatically critical and conjectured that the necessary condition is sufficient. The author presents a counterexample to the conjecture. For a graph \(G\) let \(d(G)\) and \(\delta (G)\) stand for the domatic number and the minimum degree, respectively. A graph \(G\) for which \(d(G)=\delta (G) +1\) is called domatically full. The author shows that a domatically critical graph \(G\) is domatically full if \(d(G)\leq 3\) and constructs a 4-critical graph \(K\), \(\delta (K)=4\), which is not domatically full.