The paper addresses the question of Choi, Hartke, and Kaule as to whether there are graphs for which the distinguishing chromatic number is near the chromatic number.
📌 3 Maddede Bu Makale
🎯
Amaç & Hipotez:The distinguishing chromatic number $\chi_D(G)$ of a graph $G$ is the smallest number of colors needed to properly color the vertices of $G$ such that the only automorphism of $G$ that preserves colors is the identity.
📊
Temel Bulgular & Veri:Studying the distinguishing chromatic number of graphs produced some interesting work, and in continuation, we may prefer toinvestigate the distinguishing chromatic number of the hierarchical product of graphs.
💡
Sonuç & Katkı:The paper addresses the question of Choi, Hartke, and Kaule as to whether there are graphs for which the distinguishing chromatic number is near the chromatic number.
🔬Tür:Research Article
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:chromatic number · distinguishing chromatic number · graph automorphism
Abstract
The distinguishing chromatic number $\chi_D(G)$ of a graph $G$ is the smallest number of colors needed to properly color the vertices of $G$ such that the only automorphism of $G$ that preserves colors is the identity. Studying the distinguishing chromatic number of graphs produced some interesting work, and in continuation, we may prefer toinvestigate the distinguishing chromatic number of the hierarchical product of graphs. The paper addresses the question of Choi, Hartke, and Kaule as to whether there are graphs for which the distinguishing chromatic number is near the chromatic number.
Amouzegar, T., Khashyarmanesh, K. (2026). Distinguishing chromatic number of the hierarchical product of graphs. Hacettepe Journal of Mathematics and Statistics, Volume: 55 Issue: 2. https://doi.org/10.15672/hujms.1215743
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of distinguishing colorings and partitions, Discrete Math. 343 (9), 111984, 13 pp, 2020.
M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1), 17 pp, 1996.
S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of lexicographic product of two graphs, Discussiones Mathematicae Graph Theory, 38, 853–865, 2018.
T. Amouzegar, Distinguishing number of hierarchical products of graphs, Bull. Sci. Math. 168, 102975, 2021.
N. Balachandran and S. Padinhatteeri, Distinguishing chromatic number of random Cayley graphs, Discrete Math. 340 (10), 2447–2455, 2017.
L. Barrière, F. Comellas, C. Dalfó and M. A. Fiol, The hierarchical product of graphs, Discrete Appl. Math., 157, 36–48, 2009.
M. S. Cavers, K. Seyffarth, and E. P. White, Distinguishing chromatic numbers of complements of Cartesian products of complete graphs, Discrete Math. 341 (9), 2431–2441, 2018.
M. Chan, The distinguishing number of the direct and wreath product action, J. Algebraic Combin. 24, 331–345, 2006.
Z. Che and K. L. Collins, The distinguishing chromatic number of Kneser graphs, Electron. J. Combin., 20 (1), Paper 23, 12 pp, 2013.
C.T. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin. 13 (1), 11, 12 pp, 2006.
J. Choi, S. Hartke, and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, SIAM J. Discrete Math., 24 (1), 82–100, 2010.
K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin., 13 (1), 16, 19 pp, 2006.
J. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, Boca Raton, 2004.
A. Gorzkowska, R. Kalinowski and M. Pilśniak, The distinguishing index of the Cartesian product of finite graphs, Ars Math. Contemp. 12 77-87, 2017.
W. Imrich, S. Klavžar, and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin., 14 (1), Paper 36, 12 pp, 2007.
J. Jerebic and S. Klavžar, The distinguishing chromatic number of Cartesian products of two complete graphs, Discrete Math. 310, 1715–1720, 2010.
Z. Che and K. L. Collins, The distinguishing chromatic number of Kneser graphs, Electron. J. Combin., 20 (1), Paper 23, 12 pp, 2013.