Bounds on the distinguishing chromatic number (Q2380243)

From MaRDI portal
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