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

Jerebic, Janja; Klavžar, Sandi

Discrete Math. 310, No. 12, 1715-1720 (2010).

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.

MSC:

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

Keywords:

distinguishing chromatic number; graph automorphism; Cartesian product of graphs

References:

[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