Bounds on the Distinguishing Chromatic Number - Collins, Karen L.; Hovey, Mark; Trenk, Ann N. (The Electronic Journal of Combinatorics, 2009)
Collins and Trenk define the distinguishing chromatic number $χ_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 $χ_D(G)$ based on the underlying graph $G$. In this paper we prove results that relate $χ_D(G)$ to the automorphism group of $G$. We prove two upper bounds for $χ_D(G)$ in terms of the chromatic number $χ(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} … p_k^{i_k}$ then $χ_D(G) \le χ(G) + i_1 + i_2 … + i_k$, and (2) if Aut$(G)$ is a finite and abelian group written Aut$(G) = {\Bbb Z}_{p_{1}^{i_{1}}}× … × {\Bbb Z}_{p_{k}^{i_{k}}}$ then we get the improved bound $χ_D(G) \le χ(G) + k$. In addition, we characterize automorphism groups of graphs with $χ_D(G) = 2$ and discuss similar results for graphs with $χ_D(G)=3$.