The distinguishing chromatic number of Kneser graphs (Q1953404)

Summary: 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) \geq \chi(G)\) and \(\chi_D(G) \geq D(G)\). \textit{K. L. Collins} et al. [ibid. 16, No. 1, Research Paper R88, 14 p. (2009; Zbl 1186.05051)] 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) \leq 1\). In particular, we prove that \(\chi_D(K(n,2))=\chi(K(n,2))+1\) for \(n\geq 5\). In addition, we show that \(\chi_D(K(n,r))=\chi(K(n,r))\) for \(n \geq 2r+1\) and \(r\geq 3\).