Bounds on the distinguishing chromatic number

MaRDI QIDQ2380243zbMATH OpenFDO

Authors Karen L. Collins, Ann Trenk, Mark Hovey

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/224898, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r88.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

automorphism groupdistinguishing chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Review text

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\).

Recommendations

• Graphs with large distinguishing chromatic number
• χ_D(G), |Aut(G)|, and a variant of the motion lemma
• The distinguishing chromatic number
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• The distinguishing chromatic number of Kneser graphs

Cited in

(20)

• A bound on the total chromatic number
• Proper distinguishing colorings with few colors for graphs with girth at least 5
• Graphs with large distinguishing chromatic number
• The distinguishing chromatic number of Kneser graphs
• Distinguishing chromatic number of random Cayley graphs
• The distinguishing number and distinguishing chromatic number for posets
• On the local distinguishing chromatic number
• scientific article; zbMATH DE number 5847230 (Why is no real title available?)
• Nordhaus-Gaddum theorem for the distinguishing chromatic number
• Improving upper bounds for the distinguishing index
• Distinguishing graphs by edge-colourings
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• Distinguishing chromatic numbers of wreath products
• Distinguishing maps
• On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
• Distinguishing chromatic number of middle and subdivision graphs
• Upper bounds for the list-distinguishing chromatic number
• Distinguishing chromatic numbers of complements of Cartesian products of complete graphs
• The distinguishing chromatic number
• Automorphisms and distinguishing numbers of geometric cliques

This page was built for publication: Bounds on the distinguishing chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380243)