Bounds on the distinguishing chromatic number (Q2380243): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / author | |||
Property / author: Mark A. Hovey / rank | |||
Property / author | |||
Property / author: Mark A. Hovey / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 06:55, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounds on the distinguishing chromatic number |
scientific article |
Statements
Bounds on the distinguishing chromatic number (English)
0 references
26 March 2010
0 references
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\).
0 references
distinguishing chromatic number
0 references
automorphism group
0 references