On the Locating Chromatic Number of the Cartesian Product of Graphs

Abstract

Let $c$ be a proper $k$-coloring of a connected graph $G$ and $\mathrm{\Pi }=(V_1,V_2,\dots ,V_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$, the color code of $v$ with respect to $\mathrm{\Pi }$ is defined to be the ordered $k$-tuple $c_{\mathrm{\Pi }}:=(d(v,V_1),d(v,V_2),\dots ,d(v,V_k))$, where $d(v,V_i)=min\{d(v,x)\mid x\in V_i\}$ for $1\le i\le k$. If distinct vertices have distinct color codes, then $c$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by ${\chi }_L(G)$. In this paper, we study the locating chromatic numbers of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.