Published in

Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 1(16), 2009

DOI: 10.37236/177

Links

Tools

Export citation

Search in Google Scholar

Bounds on the Distinguishing Chromatic Number

Journal article published in 2009 by Karen L. Collins, Mark Hovey, Ann N. Trenk
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Red circle
Preprint: archiving forbidden
Red circle
Postprint: archiving forbidden
Green circle
Published version: archiving allowed
Data provided by SHERPA/RoMEO

Abstract

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$.