Abstract: The dominated coloring of a graph G is a proper coloring of G such that each color class is dominated by at least one vertex. The minimum number of colors needed for a dominated coloring of G is called the dominated chromatic number of G, denoted by χdom(G). In this paper, dominated coloring of graphs is compared with (open) packing number of G and it is shown that if G is a graph of order n with diam(G) ≥ 3, then χdom(G) ≤ n−ρ(G) and if ρ0(G) = 2n/3, then χdom(G) = ρ0(G), and if ρ(G) = n/2, then χdom(G) = ρ(G). The dominated chromatic numbers of the corona of two graphs are investigated and it is shown that if µ(G) is the Mycielsky graph of G, then we have χdom(µ(G)) = χdom(G) + 1. It is also proved that the Vizing-type conjecture holds for dominated colorings of the direct product of two graphs. Finally we obtain some Nordhaus–Gaddum-type results for the dominated chromatic number χdom(G).

Keywords