Bounds on the Distinguishing Chromatic Number
Karen L. Collins, Mark Hovey, and Ann N. Trenk
In a previous paper of Collins and Trenk, we define the distinguishing
chromatic number $\chi_D(G)$ of a graph $G$ and 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) =
\bf{Z_{p_{1}^{i_{1}}}}\times \dotsb \times \bf{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$.