Turkish Journal of Mathematics
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)$.
DOI
10.3906/mat-1710-97
Keywords
Dominated coloring, dominated chromatic number, total domination number
First Page
2148
Last Page
2156
Recommended Citation
CHOOPANI, FATEMEH; JAFARZADEH, ABBAS; ERFANIAN, AHMAD; and MOJDEH, DOOST ALI
(2018)
"On dominated coloring of graphs and some Nordhaus--Gaddum-type relations,"
Turkish Journal of Mathematics: Vol. 42:
No.
5, Article 6.
https://doi.org/10.3906/mat-1710-97
Available at:
https://journals.tubitak.gov.tr/math/vol42/iss5/6
