- Turkish Journal of Mathematics
- Vol: 42 Issue: 5
- On dominated coloring of graphs and some Nordhaus--Gaddum-type relations
On dominated coloring of graphs and some Nordhaus--Gaddum-type relations
Authors : Fatemeh Choopani, Abbas Jafarzadeh, Ahmad Erfanian, Doost Ali Mojdeh
Pages : 2148-2156
View : 8 | Download : 5
Publication Date : 9999-12-31
Article Type : Makaleler
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 $\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)$.Keywords : Dominated coloring, dominated chromatic number, total domination number