The distinguishing chromatic number $\chi_{_D}(G)$ of a graph $G$ is the least integer $k$ such that there is a proper $k$-coloring of $G$ which is not preserved by any nontrivial automorphism of $G$. We study the distinguishing chromatic number of Cartesian products of graphs by focusing on how much it can exceed the trivial lower bound of the chromatic number $\chi(\cdot)$. Our main result is that for every graph $G$, there exists a constant $d_G$ such that for all $d\geq d_G$ the distinguishing chromatic number of $G^d$ is at most $\chi(G) +1$, where $G^d$ is the Cartesian product of $d$ copies of $G$. We also prove that for $d\geq5$, the Cartesian product of $d$ complete graphs has distinguishing chromatic number at most one more than the corresponding chromatic number, and we determine the distinguishing chromatic number of hypercubes exactly.
['Jeong Ok Choi', 'Stephen G. Hartke', 'Hemanshu Kaul']
Distinguishing Chromatic Number of Cartesian Products of Graphs