On Domatic Coloring of Graphs

Abstract

In this paper, we defined a k-domatic coloring of a graph G to be an assignment of colors from [k] := {1, 2, ..., k} to the vertices of G such that the closed-neighborhood of every vertex of G contains vertices of all colors from [k]. The domatic coloring number χcc(G) of G is the maximum k for which a k-domatic coloring exists. Chen et al. in [6], introduced the concept of coupon coloring for any graph with no isolated vertex. Also, Yongtang Shi et al., in [15], determined the coupon coloring number for some classes of graphs. Also, we determined the domatic coloring numbers of complete graphs, complete k-partite graphs, kneser graphs K(n, 2), Johnson graphs J(n, 2), unicyclic graphs, bicyclic graphs and generalized Θ-graphs.