The distinguishing chromatic number of Kneser graphs

Zhongyuan Che¹ ; Karen L. Collins²

¹Penn State University, Beaver Campus
²Wesleyan University

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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 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$.

Détail

DOI : 10.37236/3066

Classification : 05C15, 05C25
Mots-clés : distinguishing number, proper coloring, distinguishing chromatic number, Kneser graphs