On the dominator colorings in trees

Houcine Boumediene Merouane, and Mustapha Chellali. "On the dominator colorings in trees." Discussiones Mathematicae Graph Theory 32.4 (2012): 677-683. <http://eudml.org/doc/270842>.

@article{HoucineBoumedieneMerouane2012,
abstract = {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.},
author = {Houcine Boumediene Merouane, Mustapha Chellali},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominator coloring; domination; trees},
language = {eng},
number = {4},
pages = {677-683},
title = {On the dominator colorings in trees},
url = {http://eudml.org/doc/270842},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Houcine Boumediene Merouane
AU - Mustapha Chellali
TI - On the dominator colorings in trees
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 677
EP - 683
AB - 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.
LA - eng
KW - dominator coloring; domination; trees
UR - http://eudml.org/doc/270842
ER -