Bounds on the Distinguishing Chromatic Number
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) χ(G) + i_1 + i_2 … + i_k, and (2) if Aut(G) is a finite and abelian group written Aut(G) = Z_p_1^i_1 × … × Z_p_k^i_k then we get the improved bound χ_D(G) χ(G) + k. In addition, we characterize automorphism groups of graphs with χ_D(G) = 2 and discuss similar results for graphs with χ_D(G)=3. , number=1, journal=The Electronic Journal of Combinatorics, author=Collins, Karen L. and Hovey, Mark and Trenk, Ann N., year=2009, month=Jul., pages=#R88