Bounds on the Distinguishing Chromatic Number

Abstract

Collins and Trenk define the distinguishing chromatic number $\chi_D(G)$ of a graph $G$ to be the minimum number of colors needed to properly color the vertices of $G$ so that the only automorphism of $G$ that preserves colors is the identity. They prove results about $\chi_D(G)$ based on the underlying graph $G$. In this paper we prove results that relate $\chi_D(G)$ to the automorphism group of $G$. We prove two upper bounds for $\chi_D(G)$ in terms of the chromatic number $\chi(G)$ and show that each result is tight: (1) if Aut$(G)$ is any finite group of order $p_1^{i_1} p_2^{i_2} \cdots p_k^{i_k}$ then $\chi_D(G) \le \chi(G) + i_1 + i_2 \cdots + i_k$, and (2) if Aut$(G)$ is a finite and abelian group written Aut$(G) = {\Bbb Z}_{p_{1}^{i_{1}}}\times \cdots \times {\Bbb Z}_{p_{k}^{i_{k}}}$ then we get the improved bound $\chi_D(G) \le \chi(G) + k$. In addition, we characterize automorphism groups of graphs with $\chi_D(G) = 2$ and discuss similar results for graphs with $\chi_D(G)=3$.