Smallest Defining Number of $r$-Regular $k$-Chromatic Graphs: $r\ne k$

Abstract

In a given graph $G$, a set $S$ of vertices with an assignment of colors is a defining set of the vertex coloring of $G$, if there exists a unique extension of the colors of $S$ to a $\chi (G)$-coloring of the vertices of $G$. A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by $d(G,\chi )$. Let $d(n,r,\chi =k)$ be the smallest defining number of all $r$-regular $k$-chromatic graphs with $n$ vertices. Mahmoodian and Mendelsohn (1999) proved that for each $n\ge m$ and each $r\ge 4$, $d(n,r,\chi =3)=2$. They raised the following question: Is it true that for every $k$, there exist $n_0(k)$ and $r_0(k)$, such that for all $n\ge n_0(k)$ and $r\ge r_0(k)$ we have $d(n,r,\chi =k)=k-1$? We show that the answer to this question is positive, and we prove that for a given $k$ and for all $n\ge 3k$, if $r\ge 2(k–1)$ then $d(n,r,\chi =k)=k-1$.