For a graph $G = (V(G), E(G))$, a dominating set $D$ is a vertex subset of $V(G)$ in which every vertex of $V(G) \setminus D$ is adjacent to a vertex in $D$. The domination number of $G$ is the minimum cardinality of a dominating set of $G$ and is denoted by $\gamma(G)$. A coloring of $G$ is a partition $C = (V_{ 1}, ... ,V_{ k})$ such that each of $V_{ i}$ in an independent set. The chromatic number is the smallest $k$ among all colorings $C = (V_{ 1}, ... ,V_{ k})$ of $G$ and is denoted by $\chi(G)$. A coloring $C = (V_{ 1}, ... ,V_{ k})$ is said to be dominator if, for all $V_{ i}$, every vertex $v \in V_{ i}$ is singleton in $V_{ i}$ or is adjacent to every vertex of $V_{ j}$. The dominator chromatic number of $G$ is the minimum $k$ of all dominator colorings of $G$ and is denoted by $\chi_{ d}(G)$. Further, a graph $G$ is $D(k)$ if $\gamma(G) = \chi(G) = \chi_{ d}(G) = k$. In this paper, for $n \geq 4k - 3$, we prove that there always exists a $D(k)$ graph of order $n$. We further prove that there is no planar $D(k)$ graph when $k \in \{ 3, 4\}$. Namely, we prove that, for a non-trivial planar graph $G$, the graph $G$ is $D(k)$ if and only if $G$ is $K_{ 2, q}$ where $q \geq 2$.
Categories: math.CO