Distinguishing chromatic numbers of complements of Cartesian products of complete graphs

作者：Cavers M S; Seyffarth K^*; White E P

来源：Discrete Mathematics, 2018, 341(9): 2431-2441.

DOI：10.1016/j.disc.2018.05.016

• Cartesian product
• Distinguishing chromatic number
• Graph colouring

The distinguishing chromatic number of a graph, G, is the minimum number of colours required to properly colour the vertices of G so that the only automorphism of G that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klavzar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large.

• 出版日期2018-9