Search

In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ is a proper vertex coloring of $$G$$ such that each color class is dominated by at least one vertex of $$G$$ . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ and the total domination number $$\gamma _t(G)$$ ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ . We also give some bounds for planar and star-free graphs and exact values for split graphs. [ABSTRACT FROM AUTHOR]