On the dominator colorings in trees
Mustapha Chellali, Hocine Boumediene Merouane · Discussiones Mathematicae Graph Theory · 2012
In a graph G, a vertex is said to dominate itself and all its neighbors.A dominating set of a graph G is a subset of vertices that dominates every vertex of G.The domination number γ(G) is the minimum cardinality of a dominating set of G.A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors.A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices of at least one color class (possibly its own class).The dominator chromatic number χ d (G) is the minimum number of color classes in a dominator coloring of G. Gera showed that every nontrivial tree T satisfies γ(T ) + 1 ≤ χ d (T ) ≤ γ(T ) + 2. In this note we characterize nontrivial trees T attaining each bound.