Distinguishing chromatic number of the hierarchical product of graphs

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.

Keywords

• chromatic number
• distinguishing chromatic number
• graph automorphism
• vertex coloring
• hierarchical product of graphs

References

1. [1] B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of distinguishing colorings and partitions, Discrete Math. 343 (9), 111984, 13 pp, 2020.
2. [2] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1), 17 pp, 1996.
3. [3] S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of lexicographic product of two graphs, Discussiones Mathematicae Graph Theory, 38, 853–865, 2018.
4. [4] T. Amouzegar, Distinguishing number of hierarchical products of graphs, Bull. Sci. Math. 168, 102975, 2021.
5. [5] N. Balachandran and S. Padinhatteeri, Distinguishing chromatic number of random Cayley graphs, Discrete Math. 340 (10), 2447–2455, 2017.
6. [6] L. Barrière, F. Comellas, C. Dalfó and M. A. Fiol, The hierarchical product of graphs, Discrete Appl. Math., 157, 36–48, 2009.
7. [7] 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.
8. [8] M. Chan, The distinguishing number of the direct and wreath product action, J. Algebraic Combin. 24, 331–345, 2006.

9. [9] Z. Che and K. L. Collins, The distinguishing chromatic number of Kneser graphs, Electron. J. Combin., 20 (1) , Paper 23, 12 pp, 2013.
10. [10] C.T. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin. 13 (1), 11, 12 pp, 2006.
11. [11] J. Choi, S. Hartke, and H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, SIAM J. Discrete Math., 24 (1), 82–100, 2010.
12. [12] K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin., 13 (1), 16, 19 pp, 2006.
13. [13] J. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, Boca Raton, 2004.
14. [14] 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.
15. [15] W. Imrich, S. Klavžar, and V. Trofimov, Distinguishing infinite graphs, Electron. J. Combin., 14 (1), Paper 36, 12 pp, 2007.
16. [16] J. Jerebic and S. Klavžar, The distinguishing chromatic number of Cartesian products of two complete graphs, Discrete Math. 310, 1715–1720, 2010.