Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 1(16), 2009
DOI: 10.37236/177
Full text: Download
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}}}\times ⋯ \times {\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$.