Abstract

Graph coloring theory and domination in graphs are two major areas within graph theory which have been extensively studied. A set $S\subset V$ is said to be a dominating set of $G$ if every vertex $v \in V-S$ is adjacent to a vertex in $S$. If further, $S$ is independent, then $S$ is called an independent dominating set of $G$. The minimum cardinality of an independent dominating set is called independent domination number of $G$ and is denoted by $i(G)$.The fundamental parameter in the theory of graph coloring is the chromatic number $\chi(G)$ of a graph $G$ which is defined to be the minimum number of colors required to color the vertices of $G$ in such a way that no two adjacent vertices of $G$ receive the same color. A vertex $v \in V$ is a dominator of a set $S \subseteq V$ if $v$ dominates every vertex in $S$. A partition $\Pi = \{V_1,V_2,...,V_k\}$ is called a dominator partition if every vertex $v \in V$ is a dominator of at least one $V_i$. The dominator partition number $\Pi_d(G)$ equals the minimum $k$ such that $G$ has a dominator partition of order $k$. 

If we further require that $\Pi$ be a proper coloring of $G$, then we have a dominator coloring of $G$. The dominator chromatic number $\chi_d(G)$ is the minimum number of colors required for a dominator coloring of $G$. We present some variations of this parameter and several interesting results and unsolved problems on them.

Keywords and Phrases

Fall-chromatic number, $b$-chromatic number, dominator chromatic number, global dominator chromatic number, min-dom-color number.

A.M.S. subject classification

05C15.

.....