% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P23}{20(1)}{2013} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf The Distinguishing Chromatic Number\\ of Kneser Graphs} \author{Zhongyuan Che\\ \small Dept. of Mathematics\\[-0.8ex] \small Penn State University, Beaver Campus\\[-0.8ex] \small Monaca, PA, U.S.A\\ \small\tt zxc10@psu.edu\\ \and Karen L. Collins\\ \small Dept. of Mathematics and Computer Science\\[-0.8ex] \small Wesleyan University\\[-0.8ex] \small Middletown, CT, U.S.A.\\ \small\tt kcollins@wesleyan.edu } \date{\dateline{Aug 10, 2009}{Jan 21, 2013}{Jan 29, 2013}\\ \small Mathematics Subject Classifications: 05C15, 05C25} \begin{document} \maketitle \begin{abstract} A labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ of the vertex set of a graph $G$ is said to be proper $d$-distinguishing if it is a proper coloring of $G$ and any nontrivial automorphism of $G$ maps at least one vertex to a vertex with a different label. The distinguishing chromatic number of $G$, denoted by $\chi_D(G)$, is the minimum $d$ such that $G$ has a proper $d$-distinguishing labeling. Let $\chi(G)$ be the chromatic number of $G$ and $D(G)$ be the distinguishing number of $G$. Clearly, $\chi_D(G) \ge \chi(G)$ and $\chi_D(G) \ge D(G)$. Collins, Hovey and Trenk \cite{CHT09} have given a tight upper bound on $\chi_D(G)-\chi(G)$ in terms of the order of the automorphism group of $G$, improved when the automorphism group of $G$ is a finite abelian group. The Kneser graph $K(n,r)$ is a graph whose vertices are the $r$-subsets of an $n$ element set, and two vertices of $K(n,r)$ are adjacent if their corresponding two $r$-subsets are disjoint. In this paper, we provide a class of graphs $G$, namely Kneser graphs $K(n,r)$, whose automorphism group is the symmetric group, $S_n$, such that $\chi_D(G) - \chi(G) \le 1$. In particular, we prove that $\chi_D(K(n,2))=\chi(K(n,2))+1$ for $n\ge 5$. In addition, we show that $\chi_D(K(n,r))=\chi(K(n,r))$ for $n \ge 2r+1$ and $r\ge 3$. % keywords are optional %\bigskip\noindent \textbf{Keywords:} %distinguishing number, proper coloring, distinguishing chromatic number, Kneser graphs \end{abstract} \section{Introduction} In 1996, Albertson and Collins \cite{AC96} invented the distinguishing number of a graph. It is the smallest number of colors with which the vertices of a graph can be labeled so that every non-trivial automorphism of the graph moves a label. Since then this concept has been studied extensively, including the recent work on the distinguishing number of planar graphs by Arvind, Cheng and Devanur \cite{ACD08}; augmented cubes and hypercube powers by Chan \cite{Ch08}; Cartesian products of complete graphs by Imrich, Jerebic and Klav\v{z}ar \cite{IJK08}; infinite graphs by Imrich, Klav\v{z}ar and Trofimov \cite{IKT07}; and locally finite trees by Watkins and Zhou \cite{WaZh07}. The concept has been extended beyond graphs by Tymoczko \cite{T04} and Klav\v{z}ar, Wong and Zhu \cite{KWZ06}. In 2006, Collins and Trenk \cite{CT06} created the distinguishing chromatic number of a graph. It is the smallest number of colors with which the vertices of a graph can be labeled so that no two adjacent vertices have the same color and the only automorphism of the graph that preserves color classes is the trivial automorphism. Their paper proved versions of Brooks' Theorem for both the distinguishing number and the distinguishing chromatic number. Collins, Hovey and Trenk \cite{CHT09} proved further bounds on the distinguishing chromatic number using the automorphism group of a graph, while Choi, Hartke and Kaul \cite{CHK10} provided bounds on the distinguishing chromatic number of Cartesian products of graphs. Weigand and Jacobson \cite{WJ08} gave the distinguishing and distinguishing chromatic numbers of generalized Petersen graphs. Let $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ be a labeling of the vertex set of a graph $G$. Then the labeling $f$ is called a \emph{ proper $d$-coloring} if any two adjacent vertices have different labels. The chromatic number of $G$, denoted by $\chi(G)$, is the minimum $d$ such that $G$ has a proper $d$-coloring. Albertson and Collins introduced the definition of a distinguishing labeling and the distinguishing number of a graph in \cite{AC96}, inspired from Frank Rubin's key problem \cite{R79}: Given a ring of keys with similar shape, how many colors are needed to distinguish them? A labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ is called \emph{ $d$-distinguishing} if the only automorphism of $G$ which preserves all vertex labels is the trivial automorphism, that is, any nontrivial automorphism of $G$ must map at least one vertex to a vertex with a different label. The \emph{ distinguishing number} of $G$ is the minimum $d$ such that $G$ has a $d$-distinguishing labeling, and denoted by $D(G)$. In the definition of distinguishing labeling of a graph, there is no need to require that two adjacent vertices receive different colors. To study the problem of how to store reactive chemicals so that the chemicals are uniquely identified by their storage bins, and also arranged in a way that prevents chemical reactions, Collins and Trenk introduced the definition of a proper distinguishing labeling, and the distinguishing chromatic number of a graph. \begin{definition}\rm\cite{CT06} A labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ of the vertex set of a graph $G$ is said to be \emph{proper $d$-distinguishing} if it is both a proper $d$-coloring and a $d$-distinguishing labeling of $G$. The \emph{distinguishing chromatic number} of $G$, denoted by $\chi_D(G)$, is the minimum $d$ such that $G$ has a proper $d$-distinguishing labeling. \end{definition} From the definition, $\chi_D(G) \ge \chi(G)$ and $\chi_D(G) \ge D(G)$. It is easy to see that $\chi_D(G)\le \chi(G)\cdot D(G)$, by assigning ordered pairs to the vertices of $G$, where the first component represents proper coloring, and second component represents distinguishing labeling. It is tempting to believe, however, that in many cases, $\chi_D(G)$ should only be a little bit bigger than $\chi(G)$, or be bounded by the addition of a constant to the chromatic number. Let $G^t$ be the Cartesian product of $t$ copies of $G$. Choi, Hartke and Kaul \cite{CHK10} have shown that for $t\ge t_{G}$, $\chi_D(G^t)\le \chi(G^t)+1=\chi(G)+1$, where $t_{G}$ is a constant that depends on $G$. In particular, for $t\ge 5$, $\chi_D(K_{n}^{t})\le n+1$. On the other hand, let $G\circ H$ be the lexicographic product of $G$ and $H$, see \cite{IK00}. Let $G_1=C_{2k}\circ \overline{K_m}$ for $k\ge 4$. Tang \cite{T07} showed that \[\chi_D(G_1) = \chi(G_1) \cdot D(G_1) -1.\] In addition, let $G_2=C_{2k+1}\circ \overline{K_m}$ for $k\ge 3$, \[\chi_D(G_2) = \chi(G_2) \cdot D (G_2) -2- D(G_2) + \lceil (D(G_2)-1)/k\rceil.\] From these latter examples, we see that for some classes of graphs, the distinguishing chromatic number may be bounded close to its maximum value. However, the chromatic number of $C_{2k}\circ\overline{K_m}$ is 2 and the chromatic number of $C_{2k+1}\circ\overline{K_m}$ is 3, so these are very special cases. Recently, Collins, Hovey and Trenk \cite{CHT09} have provided two upper bounds on $\chi_D(G) - \chi(G)$ based on the automorphism group of $G$, and each of them is tight: (i) If $aut(G)$ is finite of order $p_1^{i_1}p_2^{i_2} \cdots p_k^{i_k}$ where the $p_i$'s are distinct primes, then $\chi_D(G)-\chi(G) \le i_1+i_2+\cdots +i_k$; (ii) If $aut(G)$ is a finite abelian group written as $aut(G)=Z_{p_1^{i_1}} \times Z_{p_2^{i_2}} \times \cdots \times Z_{p_k^{i_k}}$ where the $p_i$'s are distinct primes, then $\chi_D(G) -\chi(G) \le k$. We are interested in bounds on the distinguishing chromatic number, and in the construction of infinite families of graphs that achieve those bounds. We will provide a class of graphs $G$ whose automorphism group is the symmetric group $S_n$ and $\chi_D(G)-\chi(G) \le 1$. Let $n$ and $r$ be positive integers with $1 \le r \le \frac{n}{2}$. Let $[n]$ denote the set of integers from $1$ to $n$. The \emph{Kneser graph} $K(n,r)$ is a graph whose vertices are the $r$-subsets of $[n]$. A vertex corresponding to the $r$-subset $\{i_{1}, i_{2}, \ldots, i_{r}\}$ is denoted by $v_{\{i_{1}, i_{2}, \ldots, i_{r}\}}$ where $i_{1}, i_{2}, \ldots, i_{r}$ are integers from $[n]$. Two vertices $v_{\{i_{1}, i_{2}, \ldots, i_{r}\}}$ and $v_{\{j_{1}, j_{2}, \ldots, j_{r}\}}$ of $K(n,r)$ are adjacent if their corresponding two $r$-subsets $\{i_{1}, i_{2}, \ldots, i_{r}\}$ and $\{j_{1}, j_{2}, \ldots, j_{r}\}$ are disjoint. When $r=1$, the Kneser graph $K(n,1)$ is the complete graph $K_n$. When $n=2r$, $K(2r,r)$ is a set of disjoint edges. When $n=2r+1$, the Kneser graph $K(2r+1,r)$ is also called the odd graph. It is known that the chromatic number of $K(n,r)$ is $n-2r+2$, and the automorphism group of $K(n,r)$ is $S_n$, see \cite{HT96}, and that the distinguishing number of $K(n,r)$ is $2$ for $n\ge 6$ and $r \ge 2$, see \cite{AB07}. In this paper, we show that $\chi_D(K(n,r))-\chi(K(n,r))\le 1$ for all $n \ge 2r+1$. In particular, we show that $\chi_D(K(n,2))-\chi(K(n,2))=1$ for $n \ge 5$, and that $\chi_D(K(n,r))=\chi(K(n,r))$ for $n \ge 2r+1$ and $r\ge 3$. This answers a question raised by Weigand and Jacobson \cite{WJ08}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The distinguishing chromatic number of $K(n,2)$} In this section, we prove that the distinguishing chromatic number of $K(n,2)$ equals $n-1$ (where $n \ge 5$), which is its chromatic number $n-2$ plus $1$. We first introduce some basic definitions and notations. \begin{definition} \rm \label{D:SetPattern} Let $S$ be an independent set of $K(n,r)$ with at least two vertices. Then every pair of vertices in $S$ have nonempty intersection. If the intersection of all vertices in $S$ is $\{i\}$, a single element set containing the integer $i$, then we call $S$ a \emph{$1$-pattern} with the intersection $\{i\}$. On the other hand, if the intersection of all vertices in $S$ is an empty set, then we call $S$ a \emph{$0$-pattern}. \end{definition} It is well-known \cite{HT96} that any maximum independent set of $K(n,r)$ (where $n \ge 2r+1$) is a $1$-pattern with size $\binom{n-1}{r-1}$. We use $M_{\{i\}}$ to represent the maximum independent set of $K(n,r)$ such that the intersection of all its vertices is $\{i\}$. When $r=2$, any independent set of $K(n,2)$ with two or more vertices is either a $1$-pattern or a $0$-pattern. Moreover, any $0$-pattern independent set of $K(n,2)$ is a set of three vertices with the form $\{v_{\{i,j\}}, v_{\{i,k\}}, v_{\{j,k\}} \}$ where $i,j,k$ are three pairwise different integers from $[n]$. \begin{lemma}\rm \label{L:K(n,2)1} For any proper $(n-2)$-coloring of $K(n,2)$ where $n \ge 5$, each color class has size at least $2$. \end{lemma} \begin{proof} Let $\phi$ be a proper $(n-2)$-coloring of $K(n,2)$ with color classes $C_{i}$ for $1 \le i \le n-2$. Suppose that $\phi$ has one color class of size one, say $C_{n-2}=\{v_{\{n-1,n\}}\}$. Then no color class of $\phi$ is a $1$-pattern with the intersection $\{n-1\}$ or $\{n\}$. Otherwise, we can add the vertex $v_{\{n-1, n\}}$ into such a color class, and so $\chi(K(n,2)) \le n-3$. This is a contradiction. Therefore, we can assume that any $1$-pattern color class with the intersection $\{i\}$ satisfies $1 \le i \le n-2$. Let $S=\{v_{\{i,n-1\}} \mid 1 \le i \le n-2\} \cup \{v_{\{i,n\}} \mid 1 \le i \le n-2\} $. Then at most two vertices from $S$ can be contained in the same color class of $\phi$: either $v_{\{i,n-1\}}, v_{\{i,n\}}$, or $v_{\{i,n-1\}}, v_{\{j,n-1\}}$, or $v_{\{i,n\}}, v_{\{j,n\}}$ for some $1 \le i \neq j \le n-2$. It follows that each of $n-2$ color classes of $\phi$ contains some vertices of $S$. This is impossible since $S \subseteq K(n,2) \setminus C_{n-2}$. Therefore, $|C_i| > 1$ for $1 \le i \le n-2$. \end{proof} \begin{lemma}\rm\label{L:K(n,2)} For any proper $(n-2)$-coloring of $K(n,2)$ where $n \ge 5$, there is exactly one color class that is a $0$-pattern while all other color classes are $1$-patterns. \end{lemma} \begin{proof} Let $\phi$ be a proper $(n-2)$-coloring of $K(n,2)$ with color classes $C_{i}$ for $1 \le i \le n-2$. By Lemma \ref{L:K(n,2)1}, $|C_{i}| \ge 2$ for each $1 \le i \le n-2$. So $C_{i}$ is either a $0$-pattern or $1$-pattern. If all color classes of $\phi$ are $0$-patterns, then $|V(K(n,2))|=|\cup_{1 \le i \le n-2} C_{i}| =3 (n-2)$. This is not possible since $|V(K(n,2))|={n \choose 2} > 3(n-2)$ for $n \ge 5$. Hence, $\phi$ has at least one color class that is a $1$-pattern. If all color classes of $\phi$ are $1$-patterns, then without loss of generality, we can assume that $C_i \subseteq M_{\{i\}}$ for $1 \le i \le n-2$. It follows that vertex $v_{\{n-1,n\}}$ is not contained in any color class of $\phi$. This is a contradiction. So $\phi$ has at most $n-3$ color classes that are $1$-patterns. Assume that $C_{1}, C_{2}, \ldots, C_{k}$ are $1$-patterns of $\phi$. Then $1 \le k \le n-3$. Without loss of generality, we can assume that $C_{i} \subseteq M_{\{i\}}$ for $1 \le i \le k$. Note that $|M_{\{i\}}| = n-1$, $|M_{\{i_{1}\}} \cap M_{\{i_{2}\}}| = 1$ and $|M_{\{i_1\}} \cap M_{\{i_2\}}\cap M_{\{i_3\}}| = 0$ for distinct $i_1,i_2, i_3$. Hence, by the principle of inclusion-exclusion: \begin{eqnarray*} |\cup_{i=1}^{k} C_{i}| \le |\cup_{1\le i\le k} {M_{\{i\}}}| &=& \sum\limits_{i=1}^{k} |M_{\{i\}}| - \sum\limits_{1 \le i_{1}, i_{2} \le k} |M_{\{i_{1}\}} \cap M_{\{i_{2}\}}| \\ &=&k(n-1) -{k \choose 2} \\ &=&(n-1)+(n-2)+\cdots +(n-k). \end{eqnarray*} Now each $0$-pattern color class has size 3, and these are $C_{k+1}, C_{k+2}, $ $ \ldots, C_{n-2}$. Thus \[|\cup_{i=k+1}^{n-2} C_{i}|=3(n-2-k). \] The set of all vertices in $K(n,2)$ is equal to the union of all color classes, hence \begin{eqnarray*} {n \choose 2} &=& |\cup_{i=1}^{k} C_{i}|+|\cup_{i=k+1}^{n-2} C_{i}|\\ &\le& (n-1)+(n-2)+\cdots +(n-k)+3(n-k-2). \end{eqnarray*} Note that \[{n \choose 2} = (n-1)+(n-2)+\cdots +(n-k)+(n-k-1)+\cdots + 3+2+1.\] Hence, $3(n-k-2) \ge (n-k-1)+\cdots +3+2+1$, which implies that $k \ge n-4$, and $\phi$ has at least $n-4$ color classes that are $1$-patterns and so at most two color classes that are $0$-patterns. So $C_{i}$'s ($1 \le i \le n-4$) are $1$-patterns of $\phi$ which have intersections $\{1\}, \{2\}, \ldots, \{n-4\}$ respectively. Consider vertices $v_{\{n-3,n-2\}}$, $v_{\{n-3,n-1\}}$, $v_{\{n-3,n\}}$, $v_{\{n-2,n-1\}}$, $ v_{\{n-2,n\}}$, $v_{\{n-1,n\}}$. None is contained in any of the 1-pattern color classes $C_i$ for $1\leq i\leq n-4$, and the subgraph induced by these vertices is isomorphic to $K(4,2)$, a disjoint union of three edges. It is easy to check that any proper $2$-coloring of $K(4,2)$ has a $0$-pattern color class and a $1$-pattern color class, each of size $3$. It follows that exactly one of $C_{n-3}$ and $C_{n-2}$ is a $0$-pattern. \end{proof} %\begin{remark} \rm \noindent{\it Remark.} \ Lemma \ref{L:K(n,2)} is not true for Kneser graphs $K(n,r)$ when $r \ge 3$. For example, the following table provides a proper $3$-coloring of $K(7,3)$ where each color class is a $0$-pattern. In the table, we use $ijk$ to represent the vertex $v_{\{i,j,k\}}$ briefly. %\end{remark} \begin{center} \small \begin{tabular}{ |ccl|} \hline $C_1$ & = & \{123, 124, 125, 126, 127, 134, 135, 136, 137, 234, 235, 236, 237\} \\ \hline $C_2$ & = & \{145, 146, 147, 245, 246, 247, 345, 346, 347, 567\} \\ \hline $C_3$ & = & \{156, 157, 167, 256, 257, 267, 356, 357, 367, 456, 457, 467\} \\ \hline \end{tabular} \end{center} %\qed\\ \normalsize \medskip \begin{theorem}\rm\label{T:K(n,2)} Let $n \ge 5$. Then $\chi_D(K(n,2))=\chi(K(n,2))+1=n-1$. \end{theorem} \begin{proof} We first show that $\chi_D(K(n,2))>n-2$. Let $\phi$ be a proper $(n-2)$-coloring of $K(n,2)$ with color classes $C_i$ for $1 \le i \le n-2$. By Lemma \ref{L:K(n,2)}, we can assume that $C_i \subseteq M_{\{i\}}$ is a $1$-pattern where $1 \le i \le n-3$, and $C_{n-2}=\{v_{\{n-2, n-1\}}, v_{\{n-2, n\}}, v_{\{n-1, n\}} \}$ is a $0$-pattern. Since the automorphism group of $K(n,2)$ is $S_{n}$ by \cite{HT96}, we can consider an automorphism of $K(n,2)$ as a permutation of $[n]$. Let $\sigma$ be an automorphism of $K(n,2)$ which fixes each $i$ for $1 \le i \le n-3$ and permutes $\{n-2, n-1, n\}$. Then $\sigma$ is nontrivial and preserves all the color classes of $\phi$. We now show that $\chi_D(K(n,2)) \le n-1$. Define a proper $(n-1)$-coloring $\psi$ of $K(n,2)$ with color classes $D_{i}$ for $1 \le i \le n-1$: \begin{eqnarray*}\small D_{1}& = & M_{\{1\}} \setminus \{v_{\{1,n\}}\},\\ D_{i} & =& M_{\{i\}}\setminus \cup_{j < i} M_{\{j\}}, \mbox{ for } 2 \le i \le n-2, \\ D_{n-1} & = & \{v_{\{n-1, n\}}, v_{\{1, n\}}\}. \end{eqnarray*} \normalsize We claim that $\psi$ is also distinguishing. Note that for any $1$-pattern color class with the intersection $\{i\}$ in $K(n,2)$, the integer $i$ appears at least twice while each of other integers appears at most once. All color classes of $\psi$ are $1$-patterns: $D_{i}$ ($1 \le i \le n-2$) is a $1$-pattern with the intersection $\{i\}$, and $D_{n-1}$ is a $1$-pattern with the intersection $\{n\}$. Let $\sigma$ be an automorphism of $K(n,2)$ which preserves the above color classes. To preserve color class $D_{i}$ ($1 \le i \le n-2$), $\sigma$ fixes integer $i$ ($1 \le i \le n-2$), and to preserve color class $D_{n-1}$, $\sigma$ fixes integer $n$. It follows that $\sigma$ fixes integer $n-1$ and so $\sigma$ is trivial. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The distinguishing chromatic number of $K(n,r)$,\\where $n \ge 2r+1$ and $r \ge 3$} In this section, we show that the distinguishing chromatic number of $K(n,r)$ (where $n \ge 2r+1$ and $r \ge 3$) is equal to its chromatic number $n-2r+2$. We start with the odd graph, $K(2r+1,r)$, where $r \ge 3$. We choose a partition of its vertex set $C_1 \cup C_2 \cup C_3$ as follows. \begin{align*} C_1 &= M_{\{1\}},\\ C_2 &= M_{\{2\}}\setminus M_{\{1\}},\\ C_3 &= [M_{\{1\}} \cup M_{\{2\}}]^c. \end{align*} \begin{table}[ht] \caption{Occurrences of each integer $i$ in color classes $C_{1}, C_{2}, C_{3}$ of $K(2r+1,r)$} \centering \begin{tabular}{|c|ccc|ccc| ccc|} \hline $i$ && $C_{1}$ &&& $C_{2}$ &&& $C_{3}$ & \\ % inserts table \hline \hline $1$ && $\binom{2r}{r-1}$&&& $0$ &&& $0$& \\ \hline $2$ && $\binom{2r-1}{r-2}$ &&& $\binom{2r-1}{r-1}$&&& $0$& \\ \hline $3 \le i \le 2r+1$ && $\binom{2r-1}{r-2}$ &&& $\binom{2r-2}{r-2}$ &&& $\binom{2r-2}{r-1}$ &\\ \hline \end{tabular} \label{Ccolors} \end{table} \begin{lemma} \rm\label{L:K(2r+1,r)} The coloring $\{C_{1}, C_{2},C_{3}\}$ is a proper $3$-coloring but not a distinguishing coloring of $K(2r+1,r)$. \end{lemma} \begin{proof} It is easy to see that both $C_{1}$ and $C_{2}$ are independent sets since each vertex of $C_{1}$ contains the integer $1$, and each vertex of $C_{2}$ contains the integer $2$. Since each vertex of $C_{3}$ is a $r$-subset of $2r-1$ integers from $\{3, 4, \ldots, 2r+1\}$, any two vertices of $C_{3}$ must have a nonempty intersection. Then $C_{3}$ is also an independent set. Therefore, $\{C_{1}, C_{2}, C_{3}\}$ is a proper $3$-coloring of $K(2r+1,r)$. On the other hand, this is not a distinguishing coloring by Table \ref{Ccolors}. Let $\sigma \in S_{2r+1}$ be a nontrivial permutation which fixes integer $1$ and integer $2$ and permutes integers $3, 4, \ldots, 2r+1$, then $\sigma$ preserves each color class $C_{1}, C_{2}, C_{3}$. \end{proof} \begin{example} \rm \label{E:K(7,3)} A proper and distinguishing $3$-coloring of $K(7,3)$ which is derived from a proper $3$-coloring of $K(7,3)$ in Lemma \ref{L:K(2r+1,r)} shows that $\chi_D(K(7,3)) =3$. \end{example} In the following tables, we represent the vertex $v_{\{i,j,k\}}$ by $ijk$ briefly. Table \ref{PCK(7,3)} provides a proper $3$-coloring $\{C_{1}, C_{2}, C_{3}\}$ of $K(7,3)$ by Lemma \ref{L:K(2r+1,r)}. We remove vertices $v_{\{1,2,5\}}$ and $v_{\{1,3,4\}}$ from $C_{1}$ and add the former to $C_{2}$, and latter to $C_{3}$. Then we switch vertex $v_{\{2,3,4\}} \in C_{2}$ with vertex $v_{\{5,6,7\}} \in C_{3}$. Finally, we switch vertex $v_{\{2,4,7\}} \in C_{2}$ with vertex $v_{\{3,5,6\}} \in C_{3}$. We obtain a coloring $\{D_{1}, D_{2}, D_{3}\}$ of $K(7,3)$ in Table \ref{PDCK(7,3)}, where we underline those vertices moved around from coloring $\{C_{1}, C_{2}, C_{3}\}$. It is easy to check that $\{D_{1}, D_{2}, D_{3}\}$ is a proper $3$-coloring. \begin{table}[ht] \caption{\label{PCK(7,3)}A proper $3$-coloring of $K(7,3)$} \begin{center} \begin{tabular}{ | l l l |} \hline $C_{1}$ & = & \{123, 124, 125, 126, 127, 134, 135, 136, 137, 145,\\ && \ \ \ \ \ \ \ \ 146, 147, 156, 157, 167\} \\ \hline $C_{2}$ & = & \{234, 235, 236, 237, 245, 246, 247, 256, 257, 267\} \\ \hline $C_{3}$ & = & \{567, 467, 457, 456, 367, 357, 356, 347, 346, 345\} \\ \hline \end{tabular} \end{center} \end{table} \begin{table}[ht] \caption{\label{PDCK(7,3)}A proper and distinguishing $3$-coloring of $K(7,3)$} \begin{center} \begin{tabular}{ | l l l |} \hline $D_{1}$ & = & \{123, 124, 126, 127, 135, 136, 137, 145, \\ && \ \ \ \ \ \ \ \ 146, 147, 156, 157, 167\} \\ \hline $D_{2}$ & = & \{\underline{567}, 235, 236, 237, 245, 246, \underline{356}, 256, 257, 267, $\underline{125}$\} \\ \hline $D_{3}$ & = & \{\underline{234}, 467, 457, 456, 367, 357, \underline{247}, 347, 346, 345, $\underline{134}$\} \\ \hline \end{tabular} \end{center} \end{table} The coloring $\{D_{1}, D_{2}, D_{3}\}$ is distinguishing by Table \ref{K(7,3)}, which contains the number of occurrences of integers $1 \le i \le 7$ in each color class. Since all rows are pairwise different, the only automorphism of $K(7,3)$ which preserves color classes must be trivial. \qed\\ \begin{table}[ht] \caption{\label{K(7,3)} Occurrences of each integer $i$ in color classes $D_{1}, D_{2}, D_{3}$ of $K(7,3)$} \begin{center} \begin{tabular}{ | c | c | c | c |} \hline $i$ & $D_{1}$ & $D_{2}$ & $D_{3}$ \\ \hline\hline 1 & 13 & 1 & 1 \\ \hline 2 & 4 & 9 & 2\\ \hline 3 & 4 & 4 & 7 \\ \hline 4 & 4 & 2 & 9 \\ \hline 5 & 4 & 7 & 4 \\ \hline 6 & 5 & 6 & 4 \\ \hline 7 & 5 & 4 & 6 \\ \hline \end{tabular} \end{center} \end{table} Similar to the idea of Example \ref{E:K(7,3)}, we will construct a proper and distinguishing $3$-coloring $\{D_{1}, D_{2}, D_{3}\}$ of $K(2r+1, r)$ from the proper $3$-coloring $\{C_{1}, C_{2}, C_{3}\}$ of $K(2r+1,r)$ in Lemma \ref{L:K(2r+1,r)} by rearranging vertices among $C_{1}, C_{2}, C_{3}$. We list some special vertices of $K(2r+1,r)$ to clarify notations in this section. Those vertices are denoted as $x_{j}$ (where $1 \le j \le r-1$), and $y_1$, $y_2$, $z_1$, $z_2$. \large \begin{eqnarray*} x_j &=& v_{\{1, 2; \ 4+j, 4+j+1, \ldots, r+1; \ 2r-j, 2r-j+1, \ldots, 2r-1\}},\\ & & \normalsize \mbox{ for $1 \le j\le r-3$}.\\ x_{r-2} &=& v_{\{1, 2; \ r+2, r+3, \ldots, 2r-1\}},\\ x_{r-1} &=& v_{\{1; \ 3,4, \ldots, r+1\}},\\ y_{1} &=& v_{\{2, 3,4, \ldots, r+1\}},\\ y_{2} &=& v_{\{2; \ 4,5, \ldots, r+1; \ 2r+1\}},\\ z_{1} &=& v_{\{r+2, r+3, \ldots, 2r-1, 2r, 2r+1\}},\\ z_{2} &=& v_{\{3; \ r+2, r+3, \ldots, 2r-1, 2r\}}. \end{eqnarray*} \normalsize \noindent Examples \begin{itemize} \item If $r=3$, then the above listed vertices are \large $x_{1} = v_{\{1, 2; \ 5\}}$, $x_{2} = v_{\{1; \ 3, 4\}}$ $y_{1} = v_{\{2, 3, 4\}}$, $y_{2} = v_{\{2; \ 4; \ 7\}}$, $z_{1} = v_{\{5, 6, 7\}}$, $z_{2} = v_{\{3; \ 5, 6\}}$. \vskip .2in \normalsize \item If $r=5$, then the above listed vertices are \large $x_{1} = v_{\{1, 2; \ 5, 6; \ 9\}}$, $x_{2} = v_{\{1, 2; \ 6; \ 8, 9\}}$, $x_{3} = v_{\{1, 2; \ 7, 8, 9\}}$, $x_{4} = v_{\{1; \ 3, 4, 5, 6\}}$, $y_{1} = v_{\{2, 3,4, 5, 6\}}$, $y_{2} = v_{\{2; \ 4,5, 6; \ 11\}}$, $z_{1} = v_{\{7, 8, 9, 10, 11\}}$, $z_{2} = v_{\{3; \ 7, 8, 9, 10\}}$. \vskip .2in \normalsize \end{itemize} \normalsize \begin{table}[ht] \caption{Occurrences of each integer $i$ in the set of vertices $\{x_{j} | (1 \le j \le r-2)\}$, $\{x_{r-1}\}$, $\{y_{1}, y_{2}\}$, and $\{z_{1}, z_{2}\}$.} \centering \begin{tabular}{|c||cc|cc||ccc||ccc|} \hline $i$ & &$\{x_{j}| 1 \le j \le r-2\}$& $\{x_{r-1}\}$& & &$\{y_{1}, y_{2}\}$ & & &$\{z_{1}, z_{2}\}$ &\\ \hline $1$& &$r-2$&$1$& & &$0$& & &$0$&\\ $2$& &$r-2$&$0$ & & &$2$& & &$0$&\\ \hline \hline $3$& &$0$&$1$& & &$1$& & &$1$&\\ \hline\hline $4$& &$0$&$1$& & &$2$& & &$0$&\\ $5$& &$1$&$1$& & &$2$& & &$0$&\\ $6$& &$2$&$1$& & &$2$& & &$0$&\\ $\vdots$& &$\vdots$&$\vdots$& & &$\vdots$& & &$\vdots$&\\ $r-1$& &$r-5$&$1$& & &$2$& & &$0$&\\ $r$& &$r-4$&$1$& & &$2$& & &$0$&\\ $r+1$& &$r-3$&$1$& & &$2$& & &$0$&\\ \hline\hline $r+2$& &$1$&$0$& & &$0$& & &$2$&\\ $r+3$& &$2$&$0$& & &$0$& & &$2$&\\ $r+4$& &$3$&$0$& & &$0$& & &$2$&\\ $\vdots$& &$\vdots$&$\vdots$& & &$\vdots$& & &$\vdots$&\\ $2r-3$& &$r-4$&$0$& & &$0$& & &$2$&\\ $2r-2$& &$r-3$&$0$& & &$0$& & &$2$&\\ $2r-1$& &$r-2$&$0$& & &$0$& & &$2$&\\ \hline\hline $2r$& &$0$&$0$& & &$0$& & &$2$&\\ $2r+1$& &$0$&$0$& & &$1$& & &$1$&\\ \hline \end{tabular} \label{vertices} \end{table} \begin{theorem}\label{T:K(2r+1,r)} $\chi_D(K(2r+1,r)) = \chi(K(2r+1,r))=3$ for $r \ge 3$. \end{theorem} \begin{proof} It is known that $\chi_D(K(2r+1,r))\ge\chi(K(2r+1,r))=3$. To show that $\chi_D(K(2r+1,r)) \le 3$, we construct a proper and distinguishing $3$-coloring of $K(2r+1,r)$ with color classes $D_{1}, D_{2}, D_{3}$ as the following. \begin{eqnarray*} D_{1} &=&C_{1} \setminus \{x_{j} | 1 \le j \le r-1 \},\\ D_{2} &=& \left(C_{2} \setminus \{y_{1}, y_{2}\} \right) \cup \{x_{j} | 1 \le j \le r-2\} \cup \{z_1, z_2\},\\ D_{3} &=& \left(C_{3} \setminus \{z_{1}, z_{2}\} \right) \cup \{x_{r-1}\} \cup \{y_{1}, y_{2}\}. \end{eqnarray*} We first show that it is a proper coloring of $K(2r+1,r)$. It is clear that $D_{1}, D_{2}, D_{3}$ form a partition of the vertex set of $K(2r+1,r)$. All vertices in $D_{1}$ contain the integer $1$, so $D_{1}$ is an independent set of $K(2r+1,r)$. To show that $D_{2}$ is an independent set, first we see that its subset $\left(C_{2} \setminus \{y_{1}, y_{2}\} \right) \cup \{x_{j} | 1 \le j \le r-2\}$ is an independent set since all vertices contain the integer $2$. Note that the induced subgraph of $K(2r+1,r)$ generated by $C_{2}, C_{3}$ is a matching between two sets since it is isomorphic to $K(2r,r)$. So the vertex $z_{1} \in C_{3}$ (resp. $z_{2} \in C_{3}$) is only adjacent to vertex $y_{1} \in C_{2}$ (resp. $y_{2} \in C_{2}$). Therefore, $z_{1}, z_{2}$ are not adjacent to any vertex in $C_{2} \setminus \{y_{1}, y_{2}\}$. Moreover, $z_{1}, z_{2}$ are not adjacent to any $x_{j}$ $(1 \le j \le r-2)$ since they have at least one common integer $2r-1$. Hence, $D_{2}$ is an independent set. It remains to show that $D_{3}$ is an independent set. It is clear that its subset $(C_{3} \setminus \{z_{1},z_{2}\}) \cup \{y_{1}, y_{2}\}$ is an independent set since $y_{1}, y_{2}$ are not adjacent to any vertex in $C_{3} \setminus \{z_{1},z_{2}\}$. The only vertex in $C_{3}$ which $x_{r-1}$ is adjacent to is $z_{1}$ because they are disjoint. Hence $x_{r-1}$ is not adjacent to any vertex in $C_{3} \setminus \{z_{1},z_{2}\}$. Also $x_{r-1}$ is not adjacent to either $y_{1}$ or $y_{2}$ because they have at least one common integer $r+1$. Therefore, $D_3$ is also an independent set. \begin{table}[ht] \caption{Occurrences of each integer $i$ in color classes $D_{1}, D_{2}, D_{3}$ of $K(2r+1,r)$} \centering \begin{tabular}{|c|ccc|ccc|ccc|c|} \hline $i$ & &$D_{1}$& & &$D_{2}$ & & & $D_{3}$ & &\text{Remarks}\\ \hline \rule{0pt}{3ex}$1$& $\binom{2r}{r-1}$&$-$&$(r-1)$ & $0$& $+$ &$(r-2)$ & $0$&$+$&$1$ & GROUP 1 \\ \rule{0pt}{3ex}$2$& $\binom{2r-1}{r-2}$&$-$&$(r-2)$ & $\binom{2r-1}{r-1}$&$+$&$(r-4)$ & $0$&$+$&$2$ & \\ \hline \hline \rule{0pt}{3ex}$3$& $\binom{2r-1}{r-2}$&$-$&$1$ & $\binom{2r-2}{r-2}$&$+$&$0$ & $\binom{2r-2}{r-1}$&$+$&$1$ &GROUP 2 \\ \hline\hline \rule{0pt}{3ex}$4$& $\binom{2r-1}{r-2}$&$-$&$1$ & $\binom{2r-2}{r-2}$&$-$&$2$ & $\binom{2r-2}{r-1}$&$+$&$3$ &GROUP 3 \\ \rule{0pt}{3ex}$5$& $\binom{2r-1}{r-2}$&$-$&$2$ & $\binom{2r-2}{r-2}$&$-$&$1$ & $\binom{2r-2}{r-1}$&$+$&$3$ & \\ \rule{0pt}{3ex}$6$& $\binom{2r-1}{r-2}$&$-$&$3$ & $\binom{2r-2}{r-2}$&$+$&$0$ & $\binom{2r-2}{r-1}$&$+$&$3$ & \\ \vdots& &\vdots& & &\vdots& & &\vdots& & \\ $r-1$& $\binom{2r-1}{r-2}$&$-$&$(r-4)$ & $\binom{2r-2}{r-2}$&$+$&$(r-7)$ & $\binom{2r-2}{r-1}$&$+$&$3$ & \\ \rule{0pt}{3ex}$r$& $\binom{2r-1}{r-2}$&$-$&$(r-3)$ & $\binom{2r-2}{r-2}$&$+$&$(r-6)$ & $\binom{2r-2}{r-1}$&$+$&$3$ & \\ \rule{0pt}{3ex}$r+1$& $\binom{2r-1}{r-2}$&$-$&$(r-2)$ & $\binom{2r-2}{r-2}$&$+$&$(r-5)$ & $\binom{2r-2}{r-1}$&$+$&$3$ & \\ \hline \hline \rule{0pt}{3ex}$r+2$& $\binom{2r-1}{r-2}$&$-$&$1$ & $\binom{2r-2}{r-2}$&$+$&$3$ & $\binom{2r-2}{r-1}$&$-$&$2$ &GROUP 4 \\ \rule{0pt}{3ex}$r+3$& $\binom{2r-1}{r-2}$&$-$&$2$ & $\binom{2r-2}{r-2}$&$+$&$4$ & $\binom{2r-2}{r-1}$&$-$&$2$ & \\ \rule{0pt}{3ex}$r+4$& $\binom{2r-1}{r-2}$&$-$&$3$ & $\binom{2r-2}{r-2}$&$+$&$5$ & $\binom{2r-2}{r-1}$&$-$&$2$ & \\ \vdots& &\vdots& & &\vdots& & &\vdots& & \\ $2r-3$& $\binom{2r-1}{r-2}$&$-$&$(r-4)$ & $\binom{2r-2}{r-2}$&$+$&$(r-2)$ & $\binom{2r-2}{r-1}$&$-$&$2$ & \\ \rule{0pt}{3ex}$2r-2$& $\binom{2r-1}{r-2}$&$-$&$(r-3)$ & $\binom{2r-2}{r-2}$&$+$&$(r-1)$ & $\binom{2r-2}{r-1}$&$-$&$2$ & \\ \rule{0pt}{3ex}$2r-1$& $\binom{2r-1}{r-2}$&$-$&$(r-2)$ & $\binom{2r-2}{r-2}$&$+$&$r$ & $\binom{2r-2}{r-1}$&$-$&$2$ & \\ \hline \hline \rule{0pt}{3ex}$2r$& $\binom{2r-1}{r-2}$&$+$&$0$ & $\binom{2r-2}{r-2}$&$+$&$2$ & $\binom{2r-2}{r-1}$&$-$&$2$ &GROUP 5 \\ \rule{0pt}{3ex}$2r+1$& $\binom{2r-1}{r-2}$&$+$&$0$ & $\binom{2r-2}{r-2}$&$+$&$0$ & $\binom{2r-2}{r-1}$&$+$&$0$ & \\ \hline\end{tabular} \label{Dcolors} \end{table} It remains to show that $\{D_{1}, D_{2}, D_{3}\}$ is also a distinguishing coloring of $K(2r+1,r)$. We first construct a table where row $i$ contains the number of occurrences of integer $i$ (for each $1 \le i \le 2r+1$) in vertices $x_{j}$ ($1 \le j \le r-1$), $y_{1}, y_{2}$ and $z_{1}, z_{2}$, see Table \ref{vertices}. By Table \ref{Ccolors} and Table \ref{vertices}, we construct Table \ref{Dcolors} where row $i$ contains the number of occurrences of integer $i$ (for each $1 \le i \le 2r+1$) in color classes $D_{1}, D_{2}, D_{3}$. We will show that all rows are pairwise different from each other, and so any automorphism of $K(2r+1,r)$ which preserves the above color classes must be trivial. The groups in Table \ref{Dcolors} are determined by $D_{3}$ column. Each of the row $1$, row $2$, row $3$, row $2r$, and row $2r+1$ is distinguished by its unique entry in column $D_{3}$. The remaining rows are divided into GROUP 3 and GROUP 4 by $D_{3}$ column. Rows in GROUP 3 are pairwise distinguished from each other because of their entries in $D_{1}$ column, and rows in GROUP 4 are pairwise distinguished from each other by the same reason. Hence, all rows are pairwise different from each other. It follows that the only automorphism which preserves color classes must be trivial. Therefore, the proper $3$-coloring $\{D_{1}, D_{2}, D_{3}\}$ is also distinguishing. \end{proof} \begin{theorem}\rm\label{T:K(n,r)} Let $n$, $r$ be integers such that $n \ge 2r+1$ and $r \ge 3$. Then $\chi_D(K(n,r))=\chi(K(n,r))=n-2r+2$. \end{theorem} \begin{proof} By induction on $n$. If $n=2r+1$, then by Theorem \ref{T:K(2r+1,r)}, $\chi_D(K(2r+1,r))=\chi(K(2r+1,r))=3$ where $r \ge 3$. Assume that $\chi_D(K(n',r))=\chi(K(n',r))=n'-2r+2$ for any integer $2r+1 \le n'