Bounds on the Distinguishing Chromatic Number
Open Access
- 7 January 2009
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R88
Abstract
Collins and Trenk 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) \le \chi(G) + i_1 + i_2 \cdots + i_k$, and (2) if Aut$(G)$ is a finite and abelian group written Aut$(G) = {\Bbb Z}_{p_{1}^{i_{1}}}\times \cdots \times {\Bbb 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$.
Keywords
This publication has 9 references indexed in Scilit:
- Distinguishing Chromatic Number of Cartesian Products of GraphsSIAM Journal on Discrete Mathematics, 2010
- Distinguishing labellings of group action on vector spaces and graphsJournal of Algebra, 2006
- Distinguishing Numbers for Graphs and GroupsThe Electronic Journal of Combinatorics, 2004
- On the local distinguishing numbers of cyclesDiscrete Mathematics, 1999
- The Minimal Base Size of Primitive Solvable Permutation GroupsJournal of the London Mathematical Society, 1996
- Symmetry Breaking in GraphsThe Electronic Journal of Combinatorics, 1996
- On subgroups of an Abelian group maximal disjoint from a given subgroupPacific Journal of Mathematics, 1963
- Centers of purity in abelian groupsPacific Journal of Mathematics, 1963
- Graphs with Given Group and Given Graph-Theoretical PropertiesCanadian Journal of Mathematics, 1957