On graphs whose domination number is equal to chromatic and dominator chromatic numbers

Abstract

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\ge 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\ge 2$.