Turkish Journal of Mathematics




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 $\chi_{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)\geq3$, then $\chi_{dom}(G)\leq n-\rho(G)$ and if $\rho_0 (G)=2n/3$, then $\chi_{dom}(G)= \rho_0 (G)$, and if $\rho(G)=n/2$, then $\chi_{dom}(G)=\rho(G)$. The dominated chromatic numbers of the corona of two graphs are investigated and it is shown that if $\mu(G)$ is the Mycielsky graph of $G$, then we have $\chi_{dom} (\mu(G))=\chi_{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 $\chi_{dom}(G)$.


Dominated coloring, dominated chromatic number, total domination number

First Page


Last Page


Included in

Mathematics Commons