Bounds on the distinguishing chromatic number (Q2380243)

Summary: Collins and Trenk [\textit{K.L. Collins} and \textit{A.N. Trenk}, ``The distinguishing chromatic number'', Electron. J. Comb. 13, No. 1, Res. paper R16 (2006; Zbl 1081.05033)] 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)\leq \chi(G)+ i_1+i_2+\cdots+ i_k\), and (2) if \(\Aut(G)\) is a finite and abelian group written \(\Aut(G)= \mathbb Z_{p_1^{i_1}}\times\cdots\times \mathbb Z_{p_k^{i_k}}\) then we get the improved bound \(\chi_D(G)\leq \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\).