Bounds on the distinguishing chromatic number (Q2380243): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
 
(2 intermediate revisions by one other user not shown)
Property / author
 
Property / author: Mark A. Hovey / rank
Normal 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
    0 references
    0 references
    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

    Identifiers