The distinguishing chromatic number of Cartesian products of two complete graphs. (English) Zbl 1222.05225

Summary: A labeling of a graph \(G\) is distinguishing if it is only preserved by the trivial automorphism of \(G\). The distinguishing chromatic number of \(G\) is the smallest integer \(k\) such that \(G\) has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product \(K_k\square K_n\) is determined for all \(k\) and \(n\). In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.


05C76 Graph operations (line graphs, products, etc.)
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Albertson, M.O., Distinguishing Cartesian powers of graphs, Electron. J. combin., 12, #N17, (2005) · Zbl 1082.05047
[2] Albertson, M.O.; Collins, K.L., Symmetry breaking in graphs, Electron. J. combin., 3, #R18, (1996)
[3] Bogstad, B.; Cowen, L., The distinguishing number of hypercubes, Discrete math., 283, 29-35, (2004) · Zbl 1044.05039
[4] Chan, M., The distinguishing number of the direct and wreath product action, J. algebraic combin., 24, 331-345, (2006) · Zbl 1113.20002
[5] Cheng, C.T., On computing the distinguishing numbers of trees and forests, Electron. J. combin., 13, #R11, (2006) · Zbl 1080.05081
[6] J. Choi, S. Hartke, H. Kaul, Distinguishing chromatic number of Cartesian products of graphs, SIAM J. Discrete Math. (in press) · Zbl 1216.05030
[7] Collins, K.L.; Trenk, A.N., The distinguishing chromatic number, Electron. J. combin., 13, #R16, (2006) · Zbl 1081.05033
[8] Fisher, M.J.; Isaak, G., Distinguishing colorings of Cartesian products of complete graphs, Discrete math., 308, 2240-2246, (2008) · Zbl 1147.05029
[9] Imrich, W., Automorphismen und das kartesische produkt von graphen, Österreich. akad. wiss. math.-natur. kl. S.-B. II, 177, 203-214, (1969) · Zbl 0183.28502
[10] Imrich, W.; Jerebic, J.; Klavžar, S., The distinguishing number of Cartesian products of complete graphs, European J. combin., 29, 922-929, (2008) · Zbl 1205.05198
[11] Imrich, W.; Klavžar, S., Product graphs: structure and recognition, (2000), Wiley-Interscience New York
[12] Imrich, W.; Klavžar, S., Distinguishing Cartesian powers of graphs, J. graph theory, 53, 250-260, (2006) · Zbl 1108.05080
[13] Imrich, W.; Klavžar, S.; Trofimov, V., Distinguishing infinite graphs, Electron. J. combin., 14, #R36, (2007) · Zbl 1124.05044
[14] Klavžar, S.; Wong, T.-L.; Zhu, X., Distinguishing labelings of group action on vector spaces and graphs, J. algebra, 303, 626-641, (2006) · Zbl 1105.05031
[15] Klavžar, S.; Zhu, X., Cartesian powers of graphs can be distinguished by two labels, European J. combin., 28, 303-310, (2007) · Zbl 1105.05032
[16] Klöckl, W., On distinguishing and distinguishing chromatic numbers of hypercubes, Discuss. math. graph theory, 28, 419-429, (2008) · Zbl 1173.05020
[17] Miller, D.J., The automorphism group of a product of graphs, Proc. amer. math. soc., 25, 24-28, (1970) · Zbl 0194.25302
[18] Sabidussi, G., Graphs with given group and given graph-theoretical properties, Canad. J. math., 9, 515-525, (1957) · Zbl 0079.39202
[19] Watkins, M.E.; Zhou, X., Distinguishability of locally finite trees, Electron. J. combin., 14, #R29, (2007) · Zbl 1112.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.